Cod sursa(job #488128)

Utilizator c_adelinaCristescu Adelina c_adelina Data 27 septembrie 2010 18:49:43
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.67 kb
#include <cstdio>
#include <vector>
#include <deque>
#define pb push_back
using namespace std;

vector <int> v[100003];
deque <int> d;
int ok[100003];

void df(int k)
{
	d.pb(k);
	while (!d.empty())
	{
		k=d.front();d.pop_front();
		vector <int>::iterator it;
	    for (it=v[k].begin();it!=v[k].end();++it)
			if (!ok[*it]) 
				ok[*it]=1,d.pb(*it);
	}
}

int main()
{
	int n,m,i,a,b;
	freopen("dfs.in","r",stdin);
	freopen("dfs.out","w",stdout);
	scanf("%d %d",&n,&m);
	for (i=1;i<=m;++i)
	{
		scanf("%d %d",&a,&b);
		v[a].pb(b);v[b].pb(a);
	}
	for (i=1,m=0;i<=n;++i)
		if (!ok[i])
			ok[i]=1,++m,df(i);
	printf("%d",m);
return 0;
}