Cod sursa(job #488125)

Utilizator c_adelinaCristescu Adelina c_adelina Data 27 septembrie 2010 18:43:26
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.6 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)
{
	while (!v[k].empty())
		{
			if (!ok[v[k].back()]) 
				ok[v[k].back()]=1,df(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;
}