Pagini recente » Cod sursa (job #1738959) | Cod sursa (job #3123420) | Cod sursa (job #480352) | Cod sursa (job #2506954) | Cod sursa (job #1705371)
#include <fstream>
#include <list>
#include <vector>
#include <queue>
using namespace std;
#define NOT_VIS -1
#define VIS 1
struct Node{
int dist;
list<int> neigh;
Node(){
dist = NOT_VIS;
}
};
vector<Node> nodes;
void DFS(int cnode){
nodes[cnode].dist = VIS;
list<int>::iterator it;
for(it = nodes[cnode].neigh.begin();
it != nodes[cnode].neigh.end();
it ++){
if(nodes[*it].dist == NOT_VIS){
DFS(*it);
}
}
}
int main(){
int N, M;
int i,u,v;
ifstream in("dfs.in");
ofstream out("dfs.out");
in >> N >> M;
nodes.resize(N+1);
for(i = 0; i < M; i++){
in >> u >> v;
nodes[u].neigh.push_back(v);
nodes[v].neigh.push_back(u);
}
int counter = 0;
for(i = 1; i <= N; i++){
if(nodes[i].dist == NOT_VIS){
counter ++;
DFS(i);
}
}
out<<counter<<endl;
in.close();
out.close();
return 0;
}