Cod sursa(job #705930)

Utilizator valiro21Valentin Rosca valiro21 Data 5 martie 2012 10:44:14
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.78 kb
#include <cstdio>
#include <set>
#include <queue>
#define NMax 100001

using namespace std;

typedef queue<long> qc;
typedef set<long>::iterator it;

set<long> li[NMax];
long k,n,m,i,x,y,ii;
bool viz[NMax];

void dfs(long i)
{
	qc coada;
	coada.push(i);
	viz[i]=1;
	
	while(!coada.empty())
	{
		ii=coada.front();
		
		for(it i=li[ii].begin();i!=li[ii].end();i++)
			if(!viz[*i])
			{
				coada.push(*i);
				viz[*i]=1;
			}
		
		coada.pop();
	}
}

int main()
{
	freopen("dfs.in","rt",stdin);
	freopen("dfs.out","wt",stdout);
	
	scanf("%ld %ld",&n,&m);
	
	for(long i=1;i<=m;i++)
	{
		scanf("%ld %ld",&x,&y);
		li[x].insert(y);
		li[y].insert(x);
	}
	
	for(long i=1;i<=n;i++)
		if(!viz[i])
			dfs(i),k++;
	
	printf("%ld",k);
	
	return 0;
}