Pagini recente » Cod sursa (job #2087607) | Cod sursa (job #2857642) | Cod sursa (job #2986626) | Cod sursa (job #994271) | Cod sursa (job #373269)
Cod sursa(job #373269)
#include<stdio.h>
#define DIM 200005
#define DIM2 100005
struct nod
{
int x;
nod *urm;
} *lst[DIM],*lst2[DIM];
int n,vf,a[DIM2/20][DIM2/20],viz[DIM2],c[DIM/20],dr;
void add (int a,int b)
{
nod *p=new nod;
p->x=b;
p->urm=lst[a];
lst[a]=p;
}
void add2 (int a,int b)
{
nod *p=new nod;
p->x=b;
p->urm=lst2[a];
lst2[a]=p;
}
void read ()
{
int i,x,y,m;
scanf("%d%d",&n,&m);
for(i=1;i<=m;++i)
scanf("%d%d",&x,&y),add(x,y),add2(y,x);
}
void df1 (int x)
{
nod *p;
viz[x]=1;
for(p=lst[x];p;p=p->urm)
if(viz[p->x]==0)
df1(p->x);
}
void df2 (int x)
{
nod *p;
++viz[x];
c[++dr]=x;
for(p=lst2[x];p;p=p->urm)
if(viz[p->x]==1)
df2(p->x);
}
void solve (int x)
{
int i;
dr=0;
df1(x);
df2(x);
a[++vf][0]=dr;
for(i=1;i<=a[vf][0];++i)
a[vf][i]=c[i];
for(i=1;i<=n;++i)
if(viz[i]==1)
viz[i]=0;
}
int main ()
{
freopen("ctc.in","r",stdin);
freopen("ctc.out","w",stdout);
read ();
int i,j;
for(i=1;i<=n;++i)
if(!viz[i])
solve (i);
printf("%d\n",vf);
for(i=1;i<=vf;++i,printf("\n"))
for(j=1;j<=a[i][0];++j)
printf("%d ",a[i][j]);
return 0;
}