Pagini recente » Cod sursa (job #2377759) | Cod sursa (job #573359) | Cod sursa (job #669914) | Cod sursa (job #3246368) | Cod sursa (job #807812)
Cod sursa(job #807812)
#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();
}