Cod sursa(job #3196765)

Utilizator angifluturFlutur Angelica-Costela angiflutur Data 24 ianuarie 2024 19:09:38
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.17 kb
#include <iostream>
#include <vector>
#include <stack>

using namespace std;

void dfs_iterativ(int start, vector<vector<int>>& liste_adiacenta, vector<int>& viz) {
    stack<int> s;
    s.push(start);
    viz[start] = 1;

    while (!s.empty()) {
        int nod = s.top();
        s.pop();

        // Procesați sau afișați nodul aici (dacă este necesar)
        // Exemplu: cout << nod << " ";

        for (int vecin : liste_adiacenta[nod]) {
            if (viz[vecin] == 0) {
                viz[vecin] = 1;
                s.push(vecin);
            }
        }
    }
}

int main() {
    int n, m;
    cin >> n >> m;

    vector<vector<int>> liste_adiacenta(n + 1);
    vector<int> viz(n + 1, 0);

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

    int nr_componente = 0;

    for (int nod = 1; nod <= n; ++nod) {
        if (viz[nod] == 0) {
            ++nr_componente;
            dfs_iterativ(nod, liste_adiacenta, viz);
        }
    }

    cout << nr_componente << endl;

    return 0;
}