Cod sursa(job #3351462)

Utilizator teofilotopeniTeofil teofilotopeni Data 19 aprilie 2026 16:03:15
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.09 kb
#include <iostream>
#include <vector>
#include <queue>
using namespace std;


void DFS(vector<vector<int>>& graf, vector<bool>& vizited, int nod) {
    vizited[nod] = true;
    for (int neighbour : graf[nod]) {
        if (!vizited[neighbour]) {
            DFS(graf, vizited, neighbour);
        }
    }

}


int main() {
    freopen("dfs.in", "r", stdin);
    freopen("dfs.out", "w", stdout);
    int numar_noduri, numar_arce;
    if (!(cin >> numar_noduri >> numar_arce)) {
        return 1;
    }

    // citim arcele si construim matricea de legatura
    vector<vector<int>> graf(numar_noduri + 2);
    while (numar_arce--) {
        int baza, target;
        cin >> baza >> target;
        graf[baza].push_back(target);
        graf[target].push_back(baza);
    }

    vector<bool> vizited(numar_noduri + 2, false);
    int conex_components = 0;
    for (int starting_node = 1; starting_node <= numar_noduri; ++starting_node) {
        if (!vizited[starting_node]) {
            DFS(graf, vizited, starting_node);
            ++conex_components;
        }
    }
    cout << conex_components << "\n";
    return 0;
}