Cod sursa(job #3368320)

Utilizator robertbaciuBaciu Vlad-Robert robertbaciu Data 14 octombrie 2026 11:07:37
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.78 kb
#include <bitset>
#include <fstream>
#include <vector>

std::ifstream in("dfs.in");
std::ofstream out("dfs.out");

std::vector<std::vector<int>> graph;
std::bitset<100001> visited;

void dfs(int node) {
    visited.set(node);
    for (int next : graph[node]) {
        if (visited[next]) {
            continue;
        }
        visited.set(next);
        dfs(next);
    }
}

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

    graph.assign(n + 1, std::vector<int>());

    for (int i = 0; i < m; i++) {
        int x, y;
        in >> x >> y;
        graph[x].push_back(y);
        graph[y].push_back(x);
    }

    int cc_count = 0;
    for (int node = 1; node <= n; node++) {
        if (!visited[node]) {
            dfs(node);
            cc_count++;
        }
    }

    out << cc_count;
}