Pagini recente » Cod sursa (job #719696) | Cod sursa (job #122773) | Cod sursa (job #562773) | Cod sursa (job #369999) | Cod sursa (job #389156)
Cod sursa(job #389156)
#include<stdio.h>
#include<stdlib.h>
#define Max 100004
unsigned int n,nr,nrc=1;
long m;
unsigned int * a[Max],* at[Max];
unsigned int viz[Max],pord[Max];
void citire()
{scanf("%d%ld",&n,&m);
//alocarea memoriei;
for(unsigned int i=1;i<=n;i++)
{a[i]=(unsigned int *)realloc(a[i],sizeof(unsigned int));
a[i][0]=0;
at[i]=(unsigned int *)realloc(at[i],sizeof(unsigned int));
at[i][0]=0;
}
unsigned int x,y;
for(long i=1;i<=m;i++)
{scanf("%d%d",&x,&y);
a[x][0]++;
a[x]=(unsigned int *)realloc(a[x],(a[x][0]+1)*sizeof(unsigned int));
a[x][a[x][0]]=y;
at[y][0]++;
at[y]=(unsigned int *)realloc(at[y],(at[y][0]+1)*sizeof(unsigned int));
at[y][at[y][0]]=x;
}
}
void df(int x)
{viz[x]=1;
for(unsigned int i=1;i<=a[x][0];i++)
if(!viz[a[x][i]])
df(a[x][i]);
pord[++nr]=x;
}
void df2(int x)
{viz[x]=nrc;
for(unsigned int i=1;i<=at[x][0];i++)
if(viz[at[x][i]]==1)
df2(at[x][i]);
}
int main()
{freopen("ctc.in","r",stdin);
freopen("ctc.out","w",stdout);
citire();
for(unsigned int i=1;i<=n;i++)
if(!viz[i])
df(i);
for(unsigned int i=n;i>=1;i--)
if(viz[pord[i]]==1)
{nrc++;
df2(pord[i]);
}
nr=2;
printf("%d",nrc-1);
printf("\n");
for(unsigned int j=1;j<=n;j++)
{for(unsigned int i=1;i<=n;i++)
if(viz[i]==nr)
printf("%d ",i);
nr++;
printf("\n");
}
return 0;
}