Cod sursa(job #504546)

Utilizator razyelxrazyelx razyelx Data 28 noiembrie 2010 02:39:13
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.66 kb
#include <stdio.h>
#include <stdlib.h>
#define NMAX 50001
FILE * fin = fopen("retele.in","r");
FILE * fout = fopen("retele.out","w");
int n,nr,nrc;
int * A[NMAX], * AT[NMAX], *c[NMAX];
int postordine[NMAX], viz[NMAX];

void citire(){


	int x,y,m,i;

	fscanf(fin,"%d %d",&n,&m);

	for(i=1;i<=n;i++){
	   c[i] = (int *)realloc(c[i],sizeof(int));
	   c[i][0] = 0;
	   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(fin,"%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 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]);
     postordine[++nr] = x;
}
void dfst(int x){
     int i;
     viz[x] = 0;

     //printf(" %d",x);
     c[nrc][0]++;
     c[nrc] = (int *)realloc(c[nrc],(c[nrc][0]+1)*sizeof(int));
     c[nrc][c[nrc][0]] = x;

     for(i=1;i<=AT[x][0];++i)
	if(viz[AT[x][i]])
	  dfst(AT[x][i]);
}
void afisare(){
     int i,j;

     fprintf(fout,"%d\n", nrc);
     for(i=1;i<=nrc;i++){
		 fprintf(fout,"%d\n",c[i][0]);
	for(j=1;j<=c[i][0];j++)
	  fprintf(fout,"%d ",c[i][j]);
	fprintf(fout,"\n");
     }
}


int main(){
     int i;
     citire();
     for(i=1;i<=n;++i)
	if(!viz[i]) dfs(i);
     for(i=n;i>0;--i)
	if(viz[postordine[i]]){

	  //printf("componenta tare conexa %d", ++nrc);
	  nrc++;
	  dfst(postordine[i]);
	  printf("\n");
	}
     afisare();
     return 0;
}