Cod sursa(job #2792851)

Utilizator andreinovaNacu Andrei Emilian andreinova Data 2 noiembrie 2021 13:12:19
Problema Parcurgere DFS - componente conexe Scor 15
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.22 kb
#include <bits/stdc++.h>
using namespace std;

ifstream in("dfs.in");
ofstream out("dfs.out");
const int MAX = 100001;

class Graf
{
    int NrNoduri;
    vector<int> Adiacenta[MAX];
    bool Vizitat[MAX] = {0};
public:

    Graf(int NrNoduri);

    void AdaugaMuchie(int nod, int nodConectat);

    void Dfs(int nod);
    int DfsCompCnx (int nod);

};

Graf::Graf(int NrNoduri)
{
    this->NrNoduri = NrNoduri;
}

void Graf::AdaugaMuchie(int nod, int nodConectat)
{
    Adiacenta[nod].push_back(nodConectat);    /// Adauga elementul la lista lui v.
}


void Graf::Dfs(int nod)     //ca param si vectoru de vizitate
{
    Vizitat[nod] = 1;

    for (auto i: Adiacenta[nod])
        if (!Vizitat[i])
        {
            Dfs(i);
        }
}

int Graf::DfsCompCnx (int nod)
{
    int total = 0;
    for(int i = 0; i < NrNoduri; i++)
        if(!Vizitat[i])
        {
            Dfs(i);
            total++;
        }

    return total;
}

int main()
{
    int N, M;
    in >> N >> M;

    Graf g(N+1);
    int x, y;
    for(int i = 0; i < M; i++)
    {
        in >> x >> y;
        g.AdaugaMuchie(x, y);
    }

    g.Dfs(0);
    out << g.DfsCompCnx(0);

    return 0;
}