Cod sursa(job #463690)

Utilizator bugyBogdan Vlad bugy Data 17 iunie 2010 11:06:00
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.83 kb
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

using namespace std;
#define dim 100005
int n,nr,nrc;
int *A[dim], *AT[dim], *M[dim];
int postordine[dim],viz[dim];
//short int m[10000][10000];
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;
M[i]=(int *) realloc(M[i],sizeof(int));
M[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]=(int *)realloc(M[nrc], (M[nrc][0]+1)*sizeof(int));
	M[nrc][M[nrc][0]]=x;
//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;
}