Cod sursa(job #2786188)

Utilizator lucamLuca Mazilescu lucam Data 20 octombrie 2021 15:09:39
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.94 kb
#include <bits/stdc++.h>

#ifdef ONLINE_JUDGE
#define in std::cin
#define out std::cout
#else
std::ifstream in("sortaret.in");
std::ofstream out("sortaret.out");
#endif

template<typename T, size_t N>
constexpr size_t length_of(T (&)[N]) { return N; }

constexpr int N = 5e4 + 1, M = 1e5 + 1;
std::vector<int> g[N];
int pred[N];

void bfs(std::queue<int> &q) {
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        out << u << ' ';
        for (auto v : g[u]) {
            --pred[v];
            if (pred[v] == 0) {
                q.push(v);
            }
        }
    }
}

int main() {
    int n, m;
    in >> n >> m;
    for (int i = 0; i < m; ++i) {
        int u, v;
        in >> u >> v;
        g[u].push_back(v);
        ++pred[v];
    }
    std::queue<int> q;
    for (int i = 1; i <= n; ++i) {
        if (pred[i] == 0) {
            q.push(i);
        }
    }
    bfs(q);
}