Pagini recente » Cod sursa (job #492330) | Cod sursa (job #1123775) | Cod sursa (job #2022544) | Cod sursa (job #274318) | Cod sursa (job #1771941)
#include <bits/stdc++.h>
using namespace std;
const int Nmax = 100013;
class Graph {
private :
int nodes;
int edges;
vector <int> AdjList[Nmax];
bool used[Nmax];
void dfs (int node){
used[node] = 1;
for (int i=0;i<this->AdjList[node].size();++i){
if (!used[this->AdjList[node][i]]){
dfs(this->AdjList[node][i]);
}
}
}
public :
Graph (int n,int m){
this->nodes = n;
this->edges = m;
for (int i=1;i<=n;++i){
used[i] = 0;
AdjList[i].clear();
}
}
void addEdge(int from,int to){
this->AdjList[from].push_back(to);
}
int getConnectedComponents(){
int cnt = 0;
for (int i=1;i<=this->nodes;++i){
if (!used[i]){
++cnt;
this->dfs(i);
}
}
return cnt;
}
};
int main(){
ifstream cin("dfs.in");
ofstream cout("dfs.out");
int n,m,from,to;
cin>>n>>m;
Graph *graph = new Graph(n,m);
for (int i=0;i<m;++i){
cin>>from>>to;
graph->addEdge(from,to);
graph->addEdge(to,from);
}
cout<<graph->getConnectedComponents();
return 0;
}