Cod sursa(job #3123076)

Utilizator TedyRRolea Theodor Ioan TedyR Data 21 aprilie 2023 19:24:56
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.94 kb
#include <fstream>
#include <vector>
#include <iostream>

using namespace std;

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

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;
    fin >> N >> M;

    cout<< N<< endl;

    vector<vector<int>> lista_adiacenta(N);
    for (int i = 0; i < M; i++) {
        int x, y;
        fin >> 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);
        }
    }

    fout << nr_componente_conexe << endl;

    return 0;
}