Cod sursa(job #2796769)

Utilizator 6kmeleon6Luca Cordus 6kmeleon6 Data 8 noiembrie 2021 19:28:48
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.25 kb
#include <bits/stdc++.h>

using namespace std;

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

class Graf
{
    int nr_N, nr_M;
    vector<int> vecini[100001];

public:

    /// Constructori
    Graf() : nr_N(0), nr_M(0) {}
    Graf(int N, int M) : nr_N(N), nr_M(M) {}

    void citire();
    void DFS(int,vector<int>&);
    void conexe();
};

void Graf::citire()
{
    in >> nr_N >> nr_M;
    for (int i = 0; i < nr_M; i++)
    {
        int x, y;
        in >> x >> y;
        vecini[x].push_back(y);
        vecini[y].push_back(x);
    }
}

void Graf::DFS(int S, vector<int>& vizitat)
{
    vizitat[S] = 1;
    cout << S << " ";
    for(int i = 0; i < vecini[S].size(); i++)
    {
        if (vizitat[vecini[S][i]] ==0)
            {
                ///cout << vecini[S][i] << " ";
                DFS(vecini[S][i], vizitat);
            }
    }
}

void Graf::conexe()
{
    vector<int> vizitat;
    int nr=0, i;
    for(i = 0; i <= nr_N; i++)
        vizitat.push_back(0);

    for(i = 1; i <= nr_N; i++)
    {
        if (vizitat[i] == 0)
        {
            DFS(i,vizitat);
            nr++;
        }
    }
    out << nr;
}

int main()
{
    Graf G;
    G.citire();
    G.conexe();
return 0;
}