Cod sursa(job #2793349)

Utilizator ptr22222Petru Popescu ptr22222 Data 3 noiembrie 2021 15:01:08
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.61 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

ifstream in("dfs.in");
ofstream out("dfs.out");

const int nmax = 100010;

class Graf
{
private:
    bool orientat;
    int nrNoduri;
    vector <int> listaAdiacenta[nmax];
public:
    Graf(int nrNoduri = 0, bool orientat = false);
    int get_nrNoduri();
    void citireMuchii(int nrMuchii);
    vector<int> BFS(int start);
    void DFS(int nodCurent, bool *vizitatDFS);
    int nrComponenteConexe();
};

Graf :: Graf(int nrNoduri, bool orientat) : nrNoduri(nrNoduri), orientat(orientat)
{
    this->orientat = orientat;
    this->nrNoduri = nrNoduri;
}

int Graf::get_nrNoduri()
{
    return this->nrNoduri;
}

void Graf::citireMuchii(int nrMuchii)
{
    int nod1, nod2;
    for(int i = 0; i < nrMuchii; i++)
    {
        in >> nod1 >> nod2;
        listaAdiacenta[nod1].push_back(nod2);
        if(!orientat)
        {
            listaAdiacenta[nod2].push_back(nod1);
        }
    }
}

void Graf::DFS(int nodCurent, bool *vizitatDFS)
{
    vizitatDFS[nodCurent] = true;
    for(auto vecin:listaAdiacenta[nodCurent])
    {
        if(!vizitatDFS[vecin])
        {
            DFS(vecin, vizitatDFS);
        }
    }
}

int Graf::nrComponenteConexe()
{
    int contorComponente = 0;
    bool vizitat[nmax]={false};
    for(int i = 1; i <= nrNoduri; i++)
    {
        if(!vizitat[i])
        {
            DFS(i, vizitat);
            contorComponente++;
        }
    }
    return contorComponente;
}

int main() {
    int n, m;
    in >> n >> m;
    Graf g(n,false);
    g.citireMuchii(m);
    out << g.nrComponenteConexe();
    return 0;
}