Cod sursa(job #734755)

Utilizator ms-ninjacristescu liviu ms-ninja Data 14 aprilie 2012 19:55:32
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.7 kb
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
#define dim 100005
queue <int> q;
bool vizitat[dim];

vector <int> v[dim];

void bfs(int x)
{
	q.push(x);
	vizitat[x]=1;
	while(!q.empty())
	{
		int x=q.front();
		for(int k=0;k<v[x].size();++k)
			if(vizitat[v[x][k]]==0)
			{
				vizitat[v[x][k]]=1;
				q.push(v[x][k]);
			}
		
		q.pop();
	}
}

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