Cod sursa(job #396686)

Utilizator alexeiIacob Radu alexei Data 15 februarie 2010 18:47:46
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.91 kb

#include<stdio.h>
#include<stdlib.h>
#define NMAX 100024

//back to stone-age


int *A[NMAX];
int G[NMAX];
int viz[NMAX];

void DFS( int nod )
{
 int i=1,a1;                
 for( i=1; i<=A[nod][0]; ++i )
 {
 	a1=A[nod][i];
 	if( !viz[a1] ) 
	{
		viz[a1]=1;
		DFS(a1);
	}
 }
}

int main()
{
freopen("dfs.in","r",stdin);
freopen("dfs.out","w",stdout);

int N,M;
scanf("%d%d",&N,&M);

int i;
int a1,a2;

for(i=1; i<=N; ++i)
{
	A[i]=(int *) realloc( A[i], sizeof(int) );
	A[i][0]=0;
}

for(i=1; i<=M; ++i)
{
	scanf("%d%d",&a1,&a2);

	++A[a1][0];
	A[a1]=(int *) realloc( A[a1], (A[a1][0]+1)*sizeof(int) );

	A[a1][ A[a1][0] ]=a2;

	++A[a2][0];
	A[a2]=(int *) realloc( A[a2], (A[a2][0]+1)*sizeof(int) );

	A[a2][ A[a2][0] ]=a1;
}

int ans=0;
for( i=1; i<=N; ++i )
{
	if( !viz[i] )
	{
        	viz[i]=1;
		++ans;
		DFS(i);
	}
}

printf("%d\n",ans);
 
return 0;
}