Pagini recente » Cod sursa (job #1528989) | Cod sursa (job #486943) | Cod sursa (job #1175890) | Cod sursa (job #1911468) | Cod sursa (job #2796780)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("dfs.in");
ofstream fout("dfs.out");
#define NMAX 100001
class Graf{
private:
int n, m;
vector<int> v[NMAX];
bitset<NMAX> vizitat;
public:
void adauga_nod(int, int);
void citire_graf_neorientat();
void dfs(int);
int nr_componente_conexe();
};
void Graf::citire_graf_neorientat(){
int nrNoduri, nrMuchii;
fin >> nrNoduri >> nrMuchii;
this-> n = nrNoduri;
this-> m = nrMuchii;
for (int i=1; i<=m; i++){
int x, y;
fin >> x >> y;
v[x].push_back(y);
v[y].push_back(x);
}
}
void Graf::dfs(int nod){
vizitat[nod] = true;
for (auto it: v[nod])
if(!vizitat[it])
dfs(it);
}
int Graf::nr_componente_conexe(){
int compConexe = 0;
for (int i=1; i<= this->n ;i++)
if(!vizitat[i])
{
dfs(i);
compConexe++;
}
return compConexe;
}
int main()
{
Graf G;
G.citire_graf_neorientat();
fout<<G.nr_componente_conexe();
return 0;
}