Cod sursa(job #467567)

Utilizator LuffyBanu Lavinia Luffy Data 29 iunie 2010 14:10:30
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.3 kb
#include<stdio.h>
#include<stdlib.h>
#define dim 100009
using namespace std;

int n,m,i,k,x,y,j;
char viz[dim];
int ord[dim],*a[dim],*at[dim],*mat[dim];

void dfs(int nod)
{int i;
viz[nod]=1;

 for(i=1;i<=a[nod][0];i++)
	if(!viz[a[nod][i]])
	 dfs(a[nod][i]);
k++;
ord[k]=nod;}

void dfst(int nod)
{int i;
viz[nod]=0;

mat[k][0]++;
mat[k]=(int *)realloc(mat[k], (mat[k][0]+1)*sizeof(int));
mat[k][mat[k][0]]=nod;

 for(i=1;i<=at[nod][0];i++)
	if(viz[at[nod][i]])
	 dfst(at[nod][i]);

}

int main()
{
 FILE *f=fopen("ctc.in","r"), *g=fopen("ctc.out","w");
 
 fscanf(f,"%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++)
{fscanf(f,"%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;
}

for(i=1;i<=n;i++)
 if(!viz[i])
	dfs(i);

k=-1;
for(i=n;i>=1;i--)
 if(viz[ord[i]])
 {k++; mat[k]=(int *)realloc(mat[k],sizeof(int)); mat[k][0]=1;
  dfst(ord[i]);
 }
 
fprintf(g,"%d\n",k+1);
 for(i=0;i<=k;i++)
  {for(j=2;j<=mat[i][0];j++)
	fprintf(g,"%d ",mat[i][j]);
   fprintf(g,"\n");}
 
fclose(f);
fclose(g);
return 0;
}