Cod sursa(job #3295480)

Utilizator AdelinaAlexeAlexe Adelina AdelinaAlexe Data 5 mai 2025 23:45:04
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.95 kb
#include <iostream>
#include <vector>
#include <stack>

using namespace std;

int main() {

    ios::sync_with_stdio(false);

    int n, m;
    cin >> n >> m;

    vector<vector<int> > adj(n + 1);
    for(int i = 0; i < m; i++) {
        int x, y;
        cin >> x >> y;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }

    vector<bool> visited(n + 1, false);
    int num_components = 0;

    for(int i = 1; i <= n; i ++) {
        if(!visited[i]) {
            num_components++;

            stack<int> st;
            st.push(i);
            visited[i] = true;

            while (!st.empty()) {
                int node = st.top();
                st.pop();

                for(int neigh : adj[node]) {
                    if (!visited[neigh]) {
                        visited[neigh] = true;
                        st.push(neigh);
                    }
                }
            }

        }
    }

    cout << num_components;

    return 0;

}