Cod sursa(job #389156)

Utilizator DaicuDaicu Alexandru Daicu Data 1 februarie 2010 10:43:28
Problema Componente tare conexe Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.31 kb
#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;
}