Pagini recente » Cod sursa (job #563992) | Cod sursa (job #1859905) | Cod sursa (job #3238834) | Cod sursa (job #2330016) | Cod sursa (job #2172650)
#include <bits/stdc++.h>
using namespace std;
const int nmax = 1e5 + 10;
int n, m;
bool used[nmax];
vector < int > topo, now;
vector < int > g[nmax], gt[nmax];
vector < vector < int > > ans;
void dfs(int node) {
used[node] = 1;
for (auto &it: g[node]) {
if (used[it]) continue;
dfs(it);
}
topo.push_back(node);
}
void dfst(int node) {
used[node] = 1; now.push_back(node);
for (auto &it: gt[node]) {
if (used[it]) continue;
dfst(it);
}
}
void run_scc() {
for (int i = 1; i <= n; ++i)
if (!used[i]) dfs(i);
reverse(topo.begin(), topo.end());
memset(used, 0, sizeof(used));
for (auto &it: topo)
if (!used[it]) {
now.clear();
dfst(it);
ans.push_back(now);
}
}
void output() {
cout << ans.size() << '\n';
for (int i = 0; i < ans.size(); ++i) {
for (auto &it: ans[i])
cout << it << ' ';
cout << '\n';
}
}
int main()
{
freopen("ctc.in","r",stdin);
freopen("ctc.out","w",stdout);
ios_base :: sync_with_stdio(false);
cin >> n >> m;
for (int i = 1; i <= m; ++i) {
int x, y;
cin >> x >> y;
g[x].push_back(y);
gt[y].push_back(x);
}
run_scc();
output();
return 0;
}