Cod sursa(job #278866)
#include <stdio.h>
int N, M, nr, cnt;
int viz[100005], st[100005];
typedef struct pnod
{
int x;
pnod *a;
} *pNod;
pNod g[100006], gt[100005], comp[100005];
void DF(int nod)
{
viz[nod] = 1;
pNod q;
for (q = g[nod]; q != NULL; q = q -> a)
if (!viz[q -> x]) DF(q -> x);
st[++nr] = nod;
}
void DF2(int nod)
{
viz[nod] = 2;
pNod q;
q = new pnod; q -> x = nod; q -> a = comp[cnt]; comp[cnt] = q;
for (q = gt[nod]; q != NULL; q = q -> a)
if (viz[q -> x] != 2) DF2(q -> x);
}
int main()
{
freopen("ctc.in","r",stdin);
freopen("ctc.out","w",stdout);
int i, x, y;
pNod q;
scanf("%d %d",&N,&M);
for (i = 1; i <= M; i++)
{
scanf("%d %d", &x, &y);
q = new pnod; q -> x = y; q -> a = g[x]; g[x] = q;
q = new pnod; q -> x = x; q -> a = gt[y]; gt[y] = q;
}
for (i = 1; i <= N; i++)
if (!viz[i]) DF(i);
for (i = N; i >= 1; i--)
if (viz[st[i]] != 2)
{
cnt++;
DF2(st[i]);
}
printf("%d\n", cnt);
for (i = 1; i <= cnt; i++)
{
for (q = comp[i]; q != NULL; q = q -> a) printf("%d ",q -> x);
printf("\n");
}
return 0;
}