Cod sursa(job #2869703)

Utilizator the_horoHorodniceanu Andrei the_horo Data 11 martie 2022 19:34:34
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.74 kb
#include <array>
#include <cstdint>
#include <fstream>
#include <vector>


constexpr size_t MAX_NODES = 100000;


namespace normal {
    std::array<std::vector<size_t>, MAX_NODES> edges;
    std::array<bool, MAX_NODES> viz;

    void dfs (size_t node, std::vector<size_t> &appender) {
        viz[node] = true;

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

        appender.emplace_back(node);
    }
}


namespace transposed {
    std::array<std::vector<size_t>, MAX_NODES> edges;
    std::array<bool, MAX_NODES> viz;

    void dfs (size_t node, std::vector<size_t> &appender) {
        viz[node] = true;

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

        appender.emplace_back(node);
    }
}



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


    size_t nodeCount, edgeCount;
    in >> nodeCount >> edgeCount;

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

        normal::edges[x].emplace_back(y);
        transposed::edges[y].emplace_back(x);
    }


    std::vector<size_t> order;
    for (size_t i = 0; i != nodeCount; ++ i)
        if (!normal::viz[i])
            normal::dfs(i, order);


    std::vector<std::vector<size_t>> strongComponents;
    for (auto it = order.crbegin(); it != order.crend(); ++ it)
        if (!transposed::viz[*it]) {
            strongComponents.emplace_back();
            transposed::dfs(*it, strongComponents.back());
        }

    out << strongComponents.size() << '\n';

    for (const auto &component: strongComponents) {
        for (const auto &node: component)
            out << node + 1 << ' ';
        out << '\n';
    }
}