Cod sursa(job #807812)

Utilizator vlad.doruIon Vlad-Doru vlad.doru Data 5 noiembrie 2012 19:27:18
Problema Parcurgere DFS - componente conexe Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 0.98 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;
map<string,vector<string> > graph;
map<string,bool> visited;

void read(){
	string 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<string> neighbours;
	vector<string>::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[parseInt(i)])
			continue;
		dfs(parseInt(i));
		conexcomp++;
	}
	out<<conexcomp;
}

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