Cod sursa(job #565695)

Utilizator ms-ninjacristescu liviu ms-ninja Data 28 martie 2011 10:18:08
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.6 kb
#include <fstream>
#include <vector>
#include <bitset>
using namespace std;
#define dim 100003
vector <int> v[dim];
bitset <dim> viz;

void dfs(int nod)
{
	viz[nod]=1;
	
	for(int i=0;i<v[nod].size();++i)
		if(!viz[v[nod][i]])
			dfs(v[nod][i]);
	
}
		
		


int main()
{	ifstream fin("dfs.in");
	ofstream fout("dfs.out");
	int n, m, a, b, i;
		fin>>n >>m;
		
		for(i=1;i<=m;++i)
		{
			fin>> a >>b;
			v[a].push_back(b);
			v[b].push_back(a);
		}
		int conex=0;
		for(int i=1;i<=n;++i)
		{
			if(viz[i]==0)
			{
				++conex;
				dfs(i);
			}
		}
		fout<<conex;
	return 0;
}