Cod sursa(job #471075)

Utilizator alexeiIacob Radu alexei Data 16 iulie 2010 20:01:20
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.8 kb
#include<stdio.h>
#include<vector>
#include<algorithm>
#include<deque>
using namespace std;

// just chilling ( e admiterea la unibuc maine :p, si nu am mai codat de mult.. )

#define NMAX 100005

vector< int > G[NMAX];

bool viz[NMAX];

void dfs( int nod )
{
	vector< int >::iterator it;
	
	viz[nod]=1;
	
	for(it=G[nod].begin(); it!=G[nod].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 a1,a2;
	while( M-- )
	{
		scanf("%d%d",&a1,&a2);
		G[a1].push_back(a2);
		G[a2].push_back(a1);	
	}
	
	int ANS=0;
	for(int i=1; i<=N; ++i)
	{
		if( !viz[i] )
		{
			++ANS;
			dfs(i);
		}
	}
	
	printf("%d\n",ANS);
	
	return 0;
}