Cod sursa(job #336774)

Utilizator alex.cepoiAlexandru Cepoi alex.cepoi Data 1 august 2009 15:04:02
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.54 kb
#include <iostream>
#include <vector>
#include <bitset>
using namespace std;

#define nmax 100001

int N,M;
vector <int> V[nmax];
bitset <nmax> viz;

void df (int i)
{
	viz[i]=1;
	for (vector<int>::iterator j=V[i].begin(); j<V[i].end(); ++j)
		if (!viz[*j]) df(*j);
}

int main ()
{
	freopen ("dfs.in","r",stdin);
	freopen ("dfs.out","w",stdout);

	cin>>N>>M;
	while (M--)
	{
		int a,b; cin>>a>>b;
		V[a].push_back(b);
		V[b].push_back(a);
	}

	int sol = 0;
	for (int i=1; i<=N; ++i)
		if (!viz[i]) { df(i); sol++; }
	
	cout<<sol<<'\n';
	return 0;
}