Pagini recente » Cod sursa (job #1666018) | Cod sursa (job #1680579) | Cod sursa (job #2788181) | Cod sursa (job #1105961) | Cod sursa (job #1968438)
#include <bits/stdc++.h>
using namespace std;
const int nmax = 1e5 + 10;
int n, m;
int used[nmax];
vector < int > g[nmax], gt[nmax];
int ans;
vector < int > all, curr;
vector < vector < int > > scc;
void input() {
scanf("%d %d", &n, &m);
for (int i = 1; i <= m; ++i) {
int x, y; scanf("%d %d", &x, &y);
g[x].push_back(y);
gt[y].push_back(x);
}
}
void dfs(int node) {
used[node] = 1;
for (auto &it: g[node]) {
if (used[it]) continue;
dfs(it);
}
all.push_back(node);
}
void dfst(int node) {
used[node] = 1;
for (auto &it: gt[node]) {
if (used[it]) continue;
dfst(it);
}
curr.push_back(node);
}
void compute_scc() {
for (int i = 1; i <= n; ++i)
if (!used[i]) dfs(i);
reverse(all.begin(), all.end());
memset(used, 0, sizeof(used));
for (auto &node: all) {
if (used[node]) continue;
curr.clear(); dfst(node);
ans++; scc.push_back(curr);
}
}
void output() {
printf("%d\n", ans);
for (int i = 0; i < ans; ++i, printf("\n"))
for (auto &it: scc[i]) printf("%d ", it);
}
int main() {
freopen("ctc.in","r",stdin);
freopen("ctc.out","w",stdout);
input();
compute_scc();
output();
return 0;
}