Cod sursa(job #807815)

Utilizator vlad.doruIon Vlad-Doru vlad.doru Data 5 noiembrie 2012 19:29:14
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.95 kb
#include <fstream>
#include <string>
#include <tr1/unordered_map>
#include <sstream>
#include <map>
#include <vector>

using namespace std;
using namespace tr1;

ifstream in("dfs.in");
ofstream out("dfs.out");

int vertices, edges, conexcomp;
unordered_map<int,vector<int> > graph;
unordered_map<int,bool> visited;

void read(){
	int a,b;
	int i;
	in>>vertices>>edges;
	for(i=1;i<=edges;++i){
		in>>a>>b;
		graph[a].push_back(b);
		graph[b].push_back(a);
	}
}

string parseInt(int x){
	stringstream ss;
	ss<<x;
	return ss.str();
}

void dfs(string node){
	vector<int> neighbours;
	vector<int>::iterator it;
	neighbours=graph[node];
	visited[node]=true;
	for(it=neighbours.begin();it!=neighbours.end();++it){
		if(visited[*it])
			continue;
		dfs(*it);
	}
}

void conex(){
	int i;
	for(i=1;i<=vertices;++i){
		if(visited[i])
			continue;
		dfs(i);
		conexcomp++;
	}
	out<<conexcomp;
}

int main(){
	read();
	conex();
}