Cod sursa(job #3321623)

Utilizator g.vladGociu Vlad g.vlad Data 10 noiembrie 2025 16:38:28
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.94 kb

// https://infoarena.ro/problema/dfs

#include <fstream>
#include <vector>
#include <cstring>

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

void dfs(std::vector<unsigned>* graph, bool* found, unsigned entry) {
    found[entry] = true;
    for (unsigned node : graph[entry]) {
        if ( found[node] ) continue;
        dfs(graph, found, node);
    }
}

int main() {
    unsigned nodes, edges;

    in >> nodes >> edges;

    std::vector<unsigned> graph[100001];

    unsigned a, b;
    for(unsigned edge = 0; edge < edges; edge += 1) {
        in >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }

    bool found[100001];
    std::memset(found, 0, sizeof(bool) * 100001);

    size_t count = 0;

    for(unsigned node = 1; node <= nodes; node += 1) {
        if( found[node] ) continue;
        count += 1;
        dfs(graph, found, node);
    }

    out << count;
}