Cod sursa(job #151987)

Utilizator amadaeusLucian Boca amadaeus Data 8 martie 2008 21:10:03
Problema Parcurgere DFS - componente conexe Scor 100
Compilator c Status done
Runda Arhiva educationala Marime 0.99 kb
#include <stdio.h>
#include <stdlib.h>

#define NX 100010
#define tr( X,i) \
	for( i=X; *i != -1; i++ )

int *G[ NX ];
int V, E, col[ NX ], deg[ NX ], k;

void cit() {
	int i, u, v;
	
	scanf( "%d%d", &V, &E );
	for( ; E; E-- ) {
		scanf( "%d%d", &u, &v );
		deg[u]++, deg[v]++;
	}

	rewind( stdin );
	for( i = 1; i <= V; i++ ) {
		G[i] = (int *) malloc( (deg[i] + 1) * sizeof( int ) );
		deg[ i ] = 0;
     }

	scanf( "%d%d", &V, &E );
	for( ; E; E-- ) {
		scanf( "%d%d", &u, &v );
		G[ u ][ deg[u]++ ] = v;
		G[ v ][ deg[v]++ ] = u;
	}

	for( i = 1; i <= V; i++ )
		G[i][ deg[i] ] = -1;
}

void DFS( int u ) {
	int *v;
	
	col[ u ] = 1;
	tr( G[u], v )
		if( col[ *v ] == 0 )
			DFS( *v );
}

void rez() {
	int i;
	for( i = 1; i <= V; i++ )
		if( col[ i ] == 0 )
			k++, DFS( i );
}

void scr() {
	printf( "%d\n", k );
}

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

	cit();
	rez();
	scr();

	return 0;
}