Pagini recente » Cod sursa (job #3252757) | Cod sursa (job #3285608) | Autentificare | Cod sursa (job #3294102) | Cod sursa (job #235716)
Cod sursa(job #235716)
#include <stdio.h>
#define Nmax 100024
typedef struct nod_ { int a; nod_*x;} *pNod;
pNod l[Nmax], l2[Nmax], comp[Nmax];
int post[Nmax],n,m,cnt;
char v[Nmax];
void df(int nod)
{
v[nod] = 1;
for (pNod it=l[nod];it;it=it->x)
if (v[it->a]==0) df(it->a);
post[++post[0]] = nod;
}
void df2(int nod)
{
v[nod] = 0;
pNod q = new nod_;
q->a = nod;
q->x = comp[cnt];
comp[cnt] = q;
for (pNod it=l2[nod];it;it=it->x)
if (v[it->a]==1) df2(it->a);
}
int main()
{
freopen("ctc.in","r",stdin);
freopen("ctc.out","w",stdout);
scanf("%d%d",&n,&m);
pNod q;
int A,B;
for (int i=1;i<=m;++i)
{
scanf("%d%d",&A,&B);
q = new nod_;
q->a=B;
q->x=l[A];
l[A]=q;
q = new nod_;
q->a=A;
q->x=l2[B];
l2[B]=q;
}
for (int i=1;i<=n;++i)
if (v[i] == 0) df(i);
for (int i=n;i>0;--i)
if (v[post[i]] == 1) { ++cnt; df2(post[i]); }
printf("%d\n", cnt);
for (int i=1;i<=cnt;++i,printf("\n"))
for (pNod it=comp[i];it;it=it->x) printf("%d ", it->a);
return 0;
}