Cod sursa(job #680836)

Utilizator dragangabrielDragan Andrei Gabriel dragangabriel Data 15 februarie 2012 23:17:48
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.7 kb
#include<cstdio>
#include<vector>
#include<deque>
int a,n,i,j,k,viz[100005],m,ok,rez,b;
using namespace std;
vector<int>c[100005];
deque<int>v;

int main()
{
	freopen("dfs.in","r",stdin);
	freopen("dfs.out","w",stdout);
	scanf("%d %d/n",&m,&n);
	for (i=1;i<=n;i++) 
	{
		scanf("%d %d/n",&a,&b);
		c[b].push_back(a);
		c[a].push_back(b);
	}
	for (i=1;i<=m;i++)
	{
		if (viz[i]==0) {
			rez++;
			viz[i]=1;
			v.push_back(i);
			while (!v.empty()){
				int p=v.front();
		for(vector<int>::iterator it=c[p].begin();it!=c[p].end();it++)
		if (!viz[(*it)]) 
		{
			viz[(*it)]=1;
			k=(*it);
			v.push_back(k);
		}
			v.pop_front();
			}
		}
	}
	printf("%d\n",rez);
	return 0;
}