Cod sursa(job #3351448)

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


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

    // 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;
    queue<int> neighbours;
    for (int starting_node = 1; starting_node <= numar_noduri; ++starting_node) {
        if (vizited[starting_node]) {
            continue;
        }
        neighbours.push(starting_node);
        ++conex_components;

        while (!neighbours.empty()) {
            int current_node = neighbours.front();
            neighbours.pop();
            for (int neighbour : graf[current_node]) {
                if (!vizited[neighbour]) {
                    neighbours.push(neighbour);
                    vizited[neighbour] = true;
                }
            }
        }
    }
    cout << conex_components << "\n";
    return 0;
}