Cod sursa(job #2789345)

Utilizator Dantelogus99Gruia Gabriel Dantelogus99 Data 27 octombrie 2021 14:10:37
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.44 kb
#include <iostream>
#include <fstream>
#include <unordered_map>
#include <list>
using namespace std;

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

class Graf
{
    int nrNoduri;
    int nrMuchii;
    bool orientat;

    unordered_map<int, list<int>> listaAdiacenta;

public:
    Graf(bool o)
    {
        nrNoduri = 0;
        nrMuchii = 0;
        orientat = o;
    }

    Graf(int n, int m, bool o)
    {
        nrNoduri = n;
        nrMuchii = m;
        orientat = o;
    }

    void citireGraf()
    {
        int x, y;
        for (int i = 0; i < nrMuchii; i++)
        {
            fin >> x >> y;
            listaAdiacenta[x].push_back(y);

            if(!orientat)
                listaAdiacenta[y].push_back(x);
        }
    }

    int componenteConexe()
    {
        int cont = 0;
        vector<bool> vizitat(nrNoduri + 1, false);

        for(int i = 1; i <= nrNoduri; i++)
            if (!vizitat[i])
            {
                DFS(i, vizitat);
                cont++;
            }
        return cont;
    }

private:
    void DFS(int nodS, vector<bool>& vizitat)
    {
        vizitat[nodS] = true;

        for (auto vecin : listaAdiacenta[nodS])
            if (!vizitat[vecin])
                DFS(vecin, vizitat);
    }
};

int main()
{
    int n, m, s;
    fin >> n >> m;

    Graf G(n, m, false);
    G.citireGraf();

    fout << G.componenteConexe();
}