Cod sursa(job #527968)

Utilizator avram_florinavram florin constantin avram_florin Data 1 februarie 2011 16:41:37
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.7 kb
#include<cstdio>
#include<vector>

using namespace std;

int n,m,nr,g[100005],viz[100005];
vector <int> A[100005];

void citire()
{
	freopen("dfs.in" , "r" , stdin );
	freopen("dfs.out" , "w" , stdout );
	scanf("%d%d" , &n , &m );
	int i,x,y;
	for( i = 1 ; i <= m ; i++ )
		{
			scanf("%d%d" , &x , &y);
			A[x].push_back(y);
			A[y].push_back(x);
		}
	for( i = 1 ; i <= n ; i++ )
		g[i] = A[i].size();
}

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

int main()
{
	citire();
	int i;
	for( i = 1 ; i <= n ; i++ )
		if( !viz[i] )
			{
				nr++;
				DFS(i);
			}
	printf("%d\n" , nr );
	return 0;
}