Pagini recente » Cod sursa (job #463596) | Cod sursa (job #2064214) | Cod sursa (job #2754679) | Cod sursa (job #2534282) | Cod sursa (job #807815)
Cod sursa(job #807815)
#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();
}