Cod sursa(job #3187604)

Utilizator AlessiaFrunzaAlessia Frunza AlessiaFrunza Data 29 decembrie 2023 17:41:42
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.9 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

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

int vizitat[100005];

void dfs(int nod_curent, vector<int> lista_vecini[]) {
    vizitat[nod_curent] = 1;
    for (int vecin : lista_vecini[nod_curent]) {
        if (!vizitat[vecin])
            dfs(vecin, lista_vecini);
    }
}

int main() {
    int numar_noduri, numar_muchii;
    cin >> numar_noduri >> numar_muchii;

    vector<int> lista_vecini[numar_noduri];

    for (int i = 0; i < numar_muchii; i++) {
        int nod1, nod2;
        cin >> nod1 >> nod2;
        nod1--; nod2--; 
        lista_vecini[nod1].push_back(nod2);
        lista_vecini[nod2].push_back(nod1);
    }

    int count = 0;

    for (int i = 0; i < numar_noduri; i++) {
        if (!vizitat[i]) {
            dfs(i, lista_vecini);
            count++;
        }
    }

    cout << count << endl;

    return 0;
}