Cod sursa(job #2817503)

Utilizator schizofrenieShallan Davar schizofrenie Data 13 decembrie 2021 18:59:54
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.68 kb
#include <bits/stdc++.h>

std::vector<int> edges[50000];
bool vis[50000];

std::vector<int> ret;
void
dfs (int node) {
    vis[node] = true;

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

    ret.emplace_back(node + 1);
}

int main () {
    int n, m;
    std::ifstream f("sortaret.in");
    std::ofstream g("sortaret.out");

    f >> n >> m;

    for (int i = 0; i < m; ++ i) {
        int de, la;
        f >> de >> la;
        -- de, -- la;
        edges[de].emplace_back(la);
    }

    ret.reserve(n);
    for (int i = 0; i < n; ++ i)
        if (!vis[i])
            dfs(i);

    reverse(ret.begin(), ret.end());
    for (auto v: ret)
        g << v << ' ';

}