Pagini recente » Cod sursa (job #1645048) | Cod sursa (job #1954442) | Cod sursa (job #1631349) | Cod sursa (job #2898104) | Cod sursa (job #3030858)
#include <bits/stdc++.h>
using namespace std;
#ifndef LOCAL
ifstream in("ctc.in");
ofstream out("ctc.out");
#define cin in
#define cout out
#endif // LOCAL
const int NMAX = 1e5 + 7;
vector<int> g[NMAX];
vector<int> rg[NMAX];
vector<int> postorder;
int viz[NMAX];
int color[NMAX];
void dfs(int node) {
if(viz[node] == 1) return;
viz[node] = 1; color[node] = -1;
for(auto vec : g[node]) {
dfs(vec);
}
postorder.push_back(node);
}
void col(int node, int c) {
color[node] = c;
for(auto vec : rg[node]) {
if(color[vec] == -1) col(vec, c);
}
}
vector<vector<int>> ans;
int main()
{
int n, m; cin >> n >> m;
for(int i = 0; i < m; i++) {
int x, y; cin >> x >> y;
g[x].push_back(y);
rg[y].push_back(x);
}
for(int i = 1; i <= n; i++) dfs(i);
reverse(postorder.begin(), postorder.end());
int c = 0;
for(auto e : postorder) {
if(color[e] == -1) col(e, c++);
}
ans.resize(c);
for(int i = 1; i <= n; i++) ans[color[i]].push_back(i);
cout << ans.size() << '\n';
for(auto e : ans) {
for(auto ee : e)
cout << ee << " ";
cout << '\n';
}
return 0;
}