Pagini recente » Cod sursa (job #340178) | Cod sursa (job #245560) | Cod sursa (job #2296570) | Cod sursa (job #1210971) | Cod sursa (job #2924633)
#include <iostream>
#include <vector>
using namespace std;
const int NMAX = 1e5;
int n;
int m;
vector<vector<int>> graph;
vector<vector<int>> graphTranspose;
vector<bool> visited;
vector<int> postOrder;
vector<vector<int>> ctc;
void read() {
cin >> n >> m;
graph.resize(n + 1);
graphTranspose.resize(n + 1);
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.push_back(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() {
vector<int> postOrder;
visited.resize(n + 1);
for (int i = 1; i <= n; i++)
if (!visited[i])
dfs(i);
for (int i = 1; i <= n; i++)
if (visited[i]) {
ctc.push_back(vector<int>());
dfsTranspose(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;
}