Pagini recente » Cod sursa (job #3178586) | Cod sursa (job #1738063) | Cod sursa (job #2138164) | Cod sursa (job #2951319) | Cod sursa (job #588886)
Cod sursa(job #588886)
#include<stdio.h>
#define Nmax 101010
struct nod
{
int val;
nod* next;
} *ga[Nmax],*gt[Nmax],*rez[Nmax];
int N,M,x,y,nr,nrs,coad[Nmax],viz[Nmax];
void add(nod* &a,int q)
{
//printf("%d\n",q);
nod* p=new nod;
p->val=q;
p->next=a;
a=p;
}
void df(int x)
{ // printf("%d",x);
viz[x]=1;
// printf("!\n");
for(nod* a=ga[x];a;a=a->next)
{//printf("%d ",a->val);
if(!viz[a->val])
df(a->val);
}
coad[++nr]=x;
}
void df1(int x)
{
add(rez[nrs],x);
viz[x]=0;
for(nod* a=gt[x];a;a=a->next)
{//printf("%d ",a->val);
if(viz[a->val])
df1(a->val);
}
}
int main()
{
freopen("ctc.in","r",stdin);
freopen("ctc.out","w",stdout);
scanf("%d%d",&N,&M);
for(int i=1;i<=M;++i)
{
scanf("%d%d",&x,&y);
add(ga[x],y);
add(gt[y],x);
}
for(int i=1;i<=N;++i)
if(!viz[i])
{
df(i);
}
for(int i=N;i>=1;--i)
{
if(viz[coad[i]])
++nrs,df1(coad[i]);
}
printf("%d\n",nrs);
for(int i=1;i<=nrs;++i)
{
for(nod* a=rez[i];a;a=a->next)
{
printf("%d ",a->val);
}
printf("\n");
}
}