Cod sursa(job #2868314)

Utilizator the_horoHorodniceanu Andrei the_horo Data 10 martie 2022 21:00:42
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.91 kb
#include <array>
#include <cstdint>
#include <fstream>
#include <vector>


using i32 = int32_t;
using u32 = uint32_t;

constexpr size_t MAX_NODES = 100000;

std::array<std::vector<size_t>, MAX_NODES> edges;
size_t nodeCount;


std::array<bool, MAX_NODES> viz;
void dfs (size_t node) {
    viz[node] = true;

    for (auto to: edges[node])
        if (!viz[to])
            dfs(to);
}


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

    size_t edgeCount;
    in >> nodeCount >> edgeCount;

    for (size_t i = 0; i != edgeCount; ++ i) {
        size_t x, y;
        in >> x >> y;
        -- x, -- y;

        edges[x].emplace_back(y);
        edges[y].emplace_back(x);
    }

    size_t strongComponentCount = 0;
    for (size_t node = 0; node != nodeCount; ++ node)
        if (!viz[node]) {
            ++ strongComponentCount;
            dfs(node);
        }

    out << strongComponentCount;
}