Cod sursa(job #383770)

Utilizator alexeiIacob Radu alexei Data 17 ianuarie 2010 23:15:25
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.71 kb
#include<stdio.h>
#include<vector>
#define NMAX 100024

//Over the hills and far away

using namespace std;
vector< int > G[NMAX];

bool viz[NMAX];

void DFS( int node )
{
	viz[node]=1;
	for(vector< int >::iterator it=G[node].begin(); it!=G[node].end(); ++it )
	{
			if( !viz[*it] )
			{
				viz[*it]=1;
				DFS( *it );
			}
	}
}

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

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

	int i,a1,a2;
	for(i=1; i<=M; ++i)
	{
		scanf("%d%d",&a1,&a2);
		G[a1].push_back(a2);
		G[a2].push_back(a1);
	}

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

	printf("%d\n",ANS);

	return 0;
}