Pagini recente » Cod sursa (job #976988) | Cod sursa (job #2572664) | Cod sursa (job #2818898) | Cod sursa (job #617981) | Cod sursa (job #2784866)
#include <iostream>
#include <fstream>
#include <vector>
#include <bitset>
using namespace std;
const int NMAX = 100001;
class graf{
private:
int nrNoduri, nrMuchii;
vector<int> listaAd[NMAX];
bitset<NMAX> viz;
void dfs(const int &nod);
public:
graf(int nrNoduri, int nrMuchii) : nrNoduri(nrNoduri), nrMuchii(nrMuchii) {};
void adaugaInListaAd(const int &nod1, const int &nod2);
int nrCmpConexe();
};
void graf::adaugaInListaAd(const int &nod1, const int &nod2) {
listaAd[nod1].push_back(nod2);
listaAd[nod2].push_back(nod1);
}
void graf::dfs(const int &nod) {
for(int i = 0; i < listaAd[nod].size(); i++){
if(!viz[listaAd[nod][i]]){
viz[listaAd[nod][i]] = true;
dfs(listaAd[nod][i]);
}
}
}
int graf::nrCmpConexe() {
int nr = 0;
for(int i = 1; i <= nrNoduri; i++){
if(!viz[i]){
nr++;
viz[i] = true;
dfs(i);
}
}
return nr;
}
int main() {
ifstream fin ("dfs.in");
ofstream fout ("dfs.out");
int noduri, muchii;
fin>> noduri >> muchii;
graf G(noduri, muchii);
for(int i = 0; i < muchii; i++){
int n1, n2;
fin>>n1>> n2;
G.adaugaInListaAd(n1, n2);
}
fout<<G.nrCmpConexe();
return 0;
}