Pagini recente » Cod sursa (job #1998536) | Cod sursa (job #3031006) | Cod sursa (job #337489) | Cod sursa (job #758749) | Cod sursa (job #238546)
Cod sursa(job #238546)
#include<stdio.h>
#include<stdlib.h>
#define nmax 100006
int *a[nmax],*at[nmax],*rez[nmax];
int po[nmax],viz[nmax],n,nr,nrc;
void read()
{
freopen("ctc.in","r",stdin);
freopen("ctc.out","w",stdout);
int m,x,y,i;
scanf("%d %d",&n,&m);
for (i=1;i<=n;i++)
{
a[i]=(int *)realloc(a[i],sizeof(int));
a[i][0]=0;
at[i]=(int *)realloc(at[i],sizeof(int));
at[i][0]=0;
}
for (i=1;i<=m;i++)
{
scanf("%d %d",&x,&y);
a[x][0]++;
a[x]=(int *)realloc(a[x],(a[x][0]+1)*sizeof(int));
a[x][a[x][0]]=y;
at[y][0]++;
at[y]=(int *)realloc(at[y],(at[y][0]+1)*sizeof(int));
at[y][at[y][0]]=x;
}
}
void dfst(int x)
{
int i;
viz[x]=0;
++rez[nrc][0];
rez[nrc]=(int *)realloc(rez[nrc],(rez[nrc][0]+1)*sizeof(int));
rez[nrc][rez[nrc][0]]=x;
for (i=1;i<=at[x][0];i++)
if (viz[at[x][i]])
dfst(at[x][i]);
}
void dfs(int x)
{
int i;
viz[x]=1;
for (i=1;i<=a[x][0];i++)
if (!viz[a[x][i]])
dfs(a[x][i]);
po[++nr]=x;
}
int main()
{
read();
int i;
for (i=1;i<=n;i++)
if (!viz[i]) dfs(i);
for (i=n;i>0;i--)
if (viz[po[i]])
{
++nrc;
rez[nrc]=(int *)realloc(rez[nrc],sizeof(int));
rez[nrc][0]=0;
dfst(po[i]);
}
printf("%d",nrc);
int j;
for(i=1;i<=nrc;++i)
{
printf("\n");
for (j=1;j<=rez[i][0];++j)
printf("%d ",rez[i][j]);
}
printf("\n");
return 0;
}