Pagini recente » Cod sursa (job #563658) | Cod sursa (job #2961373) | Cod sursa (job #1579341) | Cod sursa (job #552267) | Cod sursa (job #2168602)
#include <cstdio>
#include <vector>
using namespace std;
const int NMAX = 100000;
vector <int> g[NMAX + 5], gtr[NMAX + 5], rez[NMAX + 5];
int viz[NMAX + 5], sol[NMAX + 5], ans = 0;
void dfs(int x)
{
int y; viz[x] = 1;
for (int i = 0; i < g[x].size(); ++i)
{
y = g[x][i];
if (viz[y] == 0)
dfs(y);
}
sol[++sol[0]] = x;
}
void dfs2(int x)
{
int y; viz[x] = ans;
rez[ans].push_back(x);
for (int i = 0; i < gtr[x].size(); ++i)
{
y = gtr[x][i];
if (viz[y] == 0)
dfs2(y);
}
}
int main()
{
freopen("ctc.in", "r", stdin);
freopen("ctc.out", "w", stdout);
int n, m, a, b;
scanf("%d %d", &n, &m);
for (int i = 1; i <= m; ++i)
{
scanf("%d %d", &a, &b);
g[a].push_back(b);
gtr[b].push_back(a);
}
for (int i = 1; i <= n; ++i)
if (viz[i] == 0)
dfs(i);
for (int i = 1; i <= n; ++i)
viz[i] = 0;
for (int i = n; i > 0; --i)
if (viz[sol[i]] == 0)
++ans, dfs2(sol[i]);
printf("%d\n", ans);
for (int i = 1; i <= ans; ++i)
{
for (int j = 0; j < rez[i].size(); ++j)
printf("%d ", rez[i][j]);
printf("\n");
}
return 0;
}