Cod sursa(job #2784866)

Utilizator Maria23Dutu Maria Maria23 Data 17 octombrie 2021 16:12:30
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.27 kb
#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;
}