Cod sursa(job #488130)

Utilizator c_adelinaCristescu Adelina c_adelina Data 27 septembrie 2010 18:50:49
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();
		while (!v[k].empty())
		{
			if (!ok[v[k].back()]) 
				ok[v[k].back()]=1,d.pb(v[k].back());
			v[k].pop_back();
		}
	}
}

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;
}