Pagini recente » Cod sursa (job #2857490) | Cod sursa (job #709228) | Cod sursa (job #843111) | Cod sursa (job #2263354) | Cod sursa (job #2806136)
#include <iostream>
#include <vector>
#include <queue>
#include <fstream>
using namespace std;
ifstream in("dfs.in");
ofstream out("dfs.out");
class Graf{
private:
int n,cc;
vector<vector<int>> muchii;
vector<int> viz;
public:
int getN();
void addMuchie(int x, int y);
void dfs(int x);
void dfs_init();
Graf();
Graf(int n);
};
Graf::Graf(int n){
cc = 0;
this->n = n;
vector<int> temp;
for(int i=0;i<=n;i++){
muchii.push_back(temp);
viz.push_back(0);
}
}
int Graf::getN (){
return n;
}
void Graf::addMuchie(int x, int y){
muchii[x].push_back(y);
}
void Graf::dfs(int x){
viz[x]=1;
for(auto i: muchii[x]){
if(!viz[i])dfs(i);
}
}
void Graf::dfs_init(){
for(int i=1;i<=n;i++){
if(!viz[i]){
dfs(i);
cc++;
}
}
out << cc;
}
int main(){
int n,m,s;
in >> n >> m;
Graf graf1(n);
int x, y;
for(int i=1;i<=m;i++){
in >> x >> y;
graf1.addMuchie(x,y);//adauga muchii
graf1.addMuchie(y,x);
}
graf1.dfs_init();
return 0;
}