Cod sursa(job #2863060)

Utilizator the_horoHorodniceanu Andrei the_horo Data 6 martie 2022 12:16:31
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.1 kb
#include <algorithm>
#include <array>
#include <cstdint>
#include <fstream>
#include <iterator>
#include <forward_list>
#include <vector>


using appender_t = std::front_insert_iterator<std::forward_list<size_t>>;

constexpr size_t MAX_NODES = 50000;


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


void dfs (size_t node, appender_t& appender) {
    viz[node] = true;

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

    *appender = node + 1;
}

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

    size_t n, m;
    f >> n >> m;

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

        edges[x].emplace_back(y);
    }

    std::forward_list<size_t> ans;
    {
        appender_t inserter = std::front_inserter(ans);
        for (size_t i = 0; i != n; ++ i)
            if (!viz[i])
                dfs(i, inserter);
    }

    std::copy(ans.begin(), ans.end(), std::ostream_iterator<size_t>(g, " "));
}