Cod sursa(job #2863497)

Utilizator the_horoHorodniceanu Andrei the_horo Data 6 martie 2022 20:04:04
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.72 kb
#include <array>
#include <fstream>
#include <iterator>
#include <vector>


using uint = unsigned int;
using inserter_t = std::back_insert_iterator<std::vector<uint>>;

constexpr uint MAX_NODES = 100000;


std::array<std::vector<uint>, MAX_NODES> edges;
std::array<std::vector<uint>, MAX_NODES> segde;


void dfs1 (uint node, std::vector<bool>& viz, inserter_t inserter) {
    viz[node] = true;

    for (auto to: edges[node])
        if (!viz[to])
            dfs1(to, viz, inserter);

    inserter = node;
}

void dfs2 (uint node, std::vector<bool>& viz, inserter_t inserter) {
    viz[node] = true;

    for (auto to: segde[node])
        if (!viz[to])
            dfs2(to, viz, inserter);

    inserter = node + 1;
}


int main () {
    std::ifstream f("ctc.in");
    f.exceptions(f.badbit | f.failbit | f.eofbit);
    std::ofstream g("ctc.out");

    uint n, m;
    f >> n >> m;

    for (uint i = 0; i != m; ++ i) {
        uint x, y;
        f >> x >> y;
        -- x, -- y;

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

    std::vector<uint> order;
    {
        std::vector<bool> viz(n);
        auto inserter = std::back_inserter(order);
        for (uint i = 0; i != n; ++ i)
            if (!viz[i])
                dfs1(i, viz, inserter);
    }

    std::vector<std::vector<uint>> ans;
    {
        std::vector<bool> viz(n);
        for (auto it = order.crbegin(); it != order.crend(); ++ it)
            if (!viz[*it]) {
                ans.emplace_back();
                dfs2(*it, viz, std::back_inserter(ans.back()));
            }
    }

    g << ans.size() << '\n';

    for (const auto &vec: ans) {
        std::copy(vec.begin(), vec.end(), std::ostream_iterator<uint>(g, " "));
        g << '\n';
    }
}