Cod sursa(job #463480)

Utilizator bugyBogdan Vlad bugy Data 16 iunie 2010 00:20:30
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.64 kb
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

using namespace std;
#define dim 100000
int n,nr,nrc;
int *A[dim], *AT[dim];
int postordine[dim],viz[dim],m[dim][dim];
void citire()
{//construim graful si graful transpus 
FILE *f=fopen("ctc.in","r");
int x,y,m,i;

fscanf(f,"%d%d",&n,&m);
//aloc memorie pentru gradul fiecarui varf

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=0;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;
}

}

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 DEST(int x)
{
int i;
viz[x]=0; m[nrc][0]++;  m[nrc][ m[nrc][0] ]=x;    //printf(" %d",x);
for(i=1;i<=AT[x][0];i++)
	if(viz[AT[x][i]])
		DEST(AT[x][i]);

}



int main()
{
int i;
citire();
FILE *g=fopen("ctc.out","w");
//parcurgem graful DFS, determinand ordinea varfurilor
	for(i=1;i<=n;i++)
		if(!viz[i]) DFS(i);
//parcurgem DFS graful transpus,prelucrand varfurile in postordine
	
	
	for(i=n;i>0;i--)
		if(viz[postordine[i]])
			//componenta tare conexa din care face parte varful curent nu a fost determinata
		{
		//printf("componenta tare conexa %d ",++nrc );
				nrc++;
		DEST(postordine[i]);
		
		//printf("\n");
		
		}
int j;
fprintf(g,"%d \n",nrc);
for(i=1;i<=nrc;i++)
	{for(j=1;j<=m[i][0];j++)
		fprintf(g,"%d ",m[i][j]);
	fprintf(g,"\n");
	}



	
return 0;
}