Cod sursa(job #2785226)

Utilizator andre.anghelacheAndreea Anghelache andre.anghelache Data 18 octombrie 2021 11:07:05
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.43 kb
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;

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

const int maxim = 100001;
bool vizitate[maxim];

class Graf{
    int noduri, muchii;
    //lista de adiacenta
    vector<int> listaAdiacenta[maxim];
public:
    void construieste(int start, int final);
    Graf(int noduri, int muchii);
    int numaraConexe();
    void dfs(int nodCurent);
};

void Graf::construieste(int start, int final) {
    listaAdiacenta[start].push_back(final);
    listaAdiacenta[final].push_back(start);
}

Graf::Graf(int noduri, int muchii) : noduri(noduri), muchii(muchii) {}

int Graf::numaraConexe() {
    int componenteConexe = 0;

    for(int i=1; i<noduri+1; i++)
    {
        if(!vizitate[i])
        {
            componenteConexe++;
            dfs(i);
        }
    }

    return componenteConexe;
}

void Graf::dfs(int nodCurent) {
    vizitate[nodCurent] = true;

    for(int vecin : listaAdiacenta[nodCurent])
    {
        if(!vizitate[vecin])
        {
            vizitate[vecin]=true;
            dfs(vecin);
        }
    }
}

int main() {
    int noduri, muchii, x, y;
    std::fill(std::begin(vizitate), std::begin(vizitate)+maxim, false);

    in>>noduri>>muchii;
    Graf mygraf(noduri, muchii);

    for(int i=0; i<muchii; i++)
    {
        //muchie de la x la y si de la y la x
        in>>x>>y;
        mygraf.construieste(x, y);
    }

    out<<mygraf.numaraConexe();

    return 0;
}