Pagini recente » Cod sursa (job #1026622) | Cod sursa (job #565506) | Cod sursa (job #996012) | Cod sursa (job #727908) | Cod sursa (job #807823)
Cod sursa(job #807823)
#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);
}
}
void dfs(int 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();
}