Pagini recente » Cod sursa (job #3231551) | Cod sursa (job #1871311) | Cod sursa (job #1188659) | Cod sursa (job #1495469) | Cod sursa (job #1816132)
// kosaraju
#include <bits/stdc++.h>
using namespace std;
const int NMAX = 1e5 + 1;
FILE *fin, *fout;
vector<int> v[NMAX], vt[NMAX];
vector<int> ans[NMAX];
int n, m, cnt;
int stk[NMAX], top;
bool viz[NMAX];
void dfs(int node) {
viz[node] = 1;
for (const int& x: v[node]) {
if (!viz[x])
dfs(x);
}
stk[++top] = node;
}
void dfst(int node) {
viz[node] = 0;
for (const int& x: vt[node]) {
if (viz[x])
dfst(x);
}
ans[cnt].push_back(node);
}
int main()
{
fin = fopen("ctc.in", "r");
fout = fopen("ctc.out", "w");
fscanf(fin, "%d %d", &n, &m);
for (int x, y; m; --m) {
fscanf(fin, "%d %d", &x, &y);
v[x].push_back(y);
vt[y].push_back(x);
}
for (int i = 1; i <= n; ++i) {
if (!viz[i])
dfs(i);
}
while (top) {
if (viz[stk[top]]) {
++cnt;
dfst(stk[top]);
}
--top;
}
fprintf(fout, "%d\n", cnt);
for (int i = 1; i <= cnt; ++i, fprintf(fout, "\n")) {
for (const int& x: ans[i])
fprintf(fout, "%d ", x);
}
return 0;
}