Cod sursa(job #3314319)

Utilizator tudo04Tudorache Andrei-Silviu tudo04 Data 9 octombrie 2025 13:40:25
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.1 kb
#include <iostream>
#include <vector>
#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;
    if (!(cin >> N >> M)) return 0;

    vector<vector<int>> g(N + 1);
    g.reserve(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);
    vector<int> st; 
    st.reserve(N);

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

            while (!st.empty()) {
                int u = st.back(); 
                st.pop_back();
                for (int v : g[u]) {
                    if (!vis[v]) {
                        vis[v] = 1;
                        st.push_back(v);
                    }
                }
            }
        }
    }

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