Cod sursa(job #3123054)

Utilizator TedyRRolea Theodor Ioan TedyR Data 21 aprilie 2023 19:05:25
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.85 kb
#include <iostream>
#include <vector>

using namespace std;

void DFS(int nod, vector<bool>& vizitat, vector<vector<int>>& lista_adiacenta) {
    vizitat[nod] = true;
    for (int vecin : lista_adiacenta[nod]) {
        if (!vizitat[vecin]) {
            DFS(vecin, vizitat, lista_adiacenta);
        }
    }
}

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

    vector<vector<int>> lista_adiacenta(N);
    for (int i = 0; i < M; i++) {
        int x, y;
        cin >> x >> y;
        lista_adiacenta[x-1].push_back(y-1);
        lista_adiacenta[y-1].push_back(x-1);
    }

    vector<bool> vizitat(N, false);
    int nr_componente_conexe = 0;
    for (int nod = 0; nod < N; nod++) {
        if (!vizitat[nod]) {
            nr_componente_conexe++;
            DFS(nod, vizitat, lista_adiacenta);
        }
    }

    cout << nr_componente_conexe << endl;

    return 0;
}