Pagini recente » Cod sursa (job #452744) | Cod sursa (job #1735455) | Cod sursa (job #2864097) | Cod sursa (job #549444) | Cod sursa (job #2927472)
/**
* La inceput facem o parcurgere in adancime pe graful initial si calculam o postordine
* pentru acesta. Apoi luam nodurile in ordine inversa fata de cea din postordine si
* facem cate o parcurgere in adancime pe graful transpus pentru fiecare nod nevizitat.
* Fiecare nod nevizitat impreuna cu nodurile nevizitate pe care le atinge in a doua
* parcurgere formeaza o componenta tare conexa.
* Complexitate timp: O(N + M)
* Complexitate memorie: O(N + M)
*/
#include <iostream>
#include <vector>
using namespace std;
const int NMAX = 1e5;
int n;
int m;
vector<int> graph[NMAX + 5];
vector<int> graphTranspose[NMAX + 5];
bool visited[NMAX + 5];
int idxPostOrder;
int postOrder[NMAX + 5];
vector<vector<int>> ctc;
void read() {
cin >> n >> m;
for (int i = 1; i <= m; i++) {
int a, b;
cin >> a >> b;
graph[a].push_back(b);
graphTranspose[b].push_back(a);
}
}
void dfs(int node) {
visited[node] = true;
for (int neighbour: graph[node])
if (!visited[neighbour])
dfs(neighbour);
postOrder[idxPostOrder++] = node;
}
void dfsTranspose(int node) {
visited[node] = false;
ctc.back().push_back(node);
for (int neighbour: graphTranspose[node])
if (visited[neighbour])
dfsTranspose(neighbour);
}
void computeCtc() {
for (int i = 1; i <= n; i++)
if (!visited[i])
dfs(i);
for (int i = n - 1; i >= 0; i--)
if (visited[ postOrder[i] ]) {
ctc.push_back(vector<int>());
dfsTranspose(postOrder[i]);
}
}
void print() {
cout << ctc.size() << endl;
for (vector<int> component: ctc) {
for (int node: component)
cout << node << " ";
cout << endl;
}
}
int main() {
freopen("ctc.in", "r", stdin);
freopen("ctc.out", "w", stdout);
read();
computeCtc();
print();
return 0;
}