Cod sursa(job #146907)

Utilizator mithyPopovici Adrian mithy Data 2 martie 2008 13:29:37
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.72 kb
#include <stdio.h>
#include <vector>
#define NMax 100005

int n, m, cnx, uz[NMax];
std::vector<int> a[NMax];

void citire();
void rez();
void dfs( int x );

int main()
{
	citire();
	rez();
	return 0;
}
void dfs( int x )
{
	int i, lg;

	uz[x] = 1;

	lg = a[x].size();

	for (i=0; i<lg; i++)
		if ( !uz[a[x][i]] )
			dfs( a[x][i] );
}
void rez()
{
	int i;

	for (i=1; i<=n; i++)
		if ( !uz[i] )
		{
			dfs(i);
			cnx++;
		}

	printf( "%d\n", cnx );
}
void citire()
{
	int i, x, y;

	freopen( "dfs.in", "rt", stdin );
	freopen( "dfs.out", "wt", stdout );

	scanf( "%d %d", &n, &m );

	for (i=0; i<m; i++)
	{
		scanf( "%d %d", &x, &y );
		a[x].push_back( y );
		a[y].push_back( x );
	}
}