Pagini recente » Cod sursa (job #1580530) | Cod sursa (job #558319) | Cod sursa (job #1904079) | Cod sursa (job #2495689) | Cod sursa (job #2192249)
#include <iostream>
#include <fstream>
#include <vector>
#define MAXN 100005
using namespace std;
ifstream in("dfs.in");
ofstream out("dfs.out");
class Graph{
private:
int n;
vector<int>v[MAXN];
bool viz[MAXN];
void dfs(int nod);
public:
Graph(int n);
void add_edge(int nod,int muchie);
void afis(int n);
int dfs_untill(int n);
};
Graph::Graph(int n){
this->n = n;
}
void Graph::add_edge(int nod,int muchie){
v[nod].push_back(muchie);
}
void Graph::afis(int n){
for(int i = 1; i <= n; i++){
cerr<<i<<" : ";
for(int j = 0; j < v[i].size(); j++)
cerr<<v[i][j]<<" ";
cerr<<endl;
}
}
void Graph::dfs(int nod){
viz[nod] = true;
int curent;
for(int i = 0; i < v[nod].size(); i++){
curent = v[nod][i];
if(!viz[curent])
dfs(curent);
}
}
int Graph::dfs_untill(int n){
for(int i = 1; i <= n; i++)
viz[i] = false;
int cnt = 0;
for(int i = 1; i <= n; i++){
if(!viz[i]){
cnt++;
dfs(i);
}
}
return cnt;
}
int main()
{
int n,m;
in>>n>>m;
Graph graf(n);
for(int i = 1; i <= m; i++){
int x,y;
in>>x>>y;
graf.add_edge(x,y);
graf.add_edge(y,x);
}
out<<graf.dfs_untill(n);
return 0;
}