Cod sursa(job #2789340)

Utilizator Dantelogus99Gruia Gabriel Dantelogus99 Data 27 octombrie 2021 13:57:30
Problema Parcurgere DFS - componente conexe Scor 75
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.54 kb
#include <iostream>
#include <fstream>
#include <map>
#include <list>
#include <set>
#include <stack>
#include <queue>
using namespace std;

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

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

    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;
        map<int, bool> vizitat;

        for (int i = 0; i <= nrNoduri; i++)
            vizitat.emplace(i, false);


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

private:
    void DFS(int nodS, map<int, 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();
}