Cod sursa(job #3314320)

Utilizator tudo04Tudorache Andrei-Silviu tudo04 Data 9 octombrie 2025 13:41:45
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1 kb
#include <iostream>
#include <vector>
#include <stack>
#include <cstdio>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    freopen("dfs.in", "r", stdin);
    freopen("dfs.out", "w", stdout);

    int N, M;
    cin >> N >> M;

    vector<vector<int>> g(N + 1);
    for (int i = 0; i < M; ++i) {
        int x, y;
        cin >> x >> y;
        g[x].push_back(y);
        g[y].push_back(x);
    }

    vector<char> vis(N + 1, 0);
    stack<int> st;
    int comp = 0;

    for (int i = 1; i <= N; ++i) {
        if (!vis[i]) {
            ++comp;
            st.push(i);
            vis[i] = 1;

            while (!st.empty()) {
                int u = st.top(); st.pop();
                for (int v : g[u]) {
                    if (!vis[v]) {
                        vis[v] = 1;
                        st.push(v);
                    }
                }
            }
        }
    }

    cout << comp << '\n';
    return 0;
}