cpp_src/graph/helper/TopologicalSort.hpp

• View this file on GitHub
• Last update: 2023-04-22 00:40:06+09:00
• Include: #include "cpp_src/graph/helper/TopologicalSort.hpp"

Code

// lexicographically smallest
template <class T>
V<int> topological_sort(const Graph<T>& g) {
    int n = g.size();

    priority_queue<int, V<int>, greater<int>> que;

    V<int> indeg(n);
    rep(i, n) {
        for (auto e : g[i]) {
            indeg[e.to]++;
        }
    }

    rep(i, n) if (indeg[i] == 0) que.push(i);

    V<int> res;
    while (!que.empty()) {
        int v = que.top();
        que.pop();
        res.pb(v);

        for (auto e : g[v]) {
            if (--indeg[e.to] == 0) {
                que.emplace(e.to);
            }
        }
    }

    if (SZ(res) < n) return V<int>{};
    return res;
}

#line 1 "cpp_src/graph/helper/TopologicalSort.hpp"
// lexicographically smallest
template <class T>
V<int> topological_sort(const Graph<T>& g) {
    int n = g.size();

    priority_queue<int, V<int>, greater<int>> que;

    V<int> indeg(n);
    rep(i, n) {
        for (auto e : g[i]) {
            indeg[e.to]++;
        }
    }

    rep(i, n) if (indeg[i] == 0) que.push(i);

    V<int> res;
    while (!que.empty()) {
        int v = que.top();
        que.pop();
        res.pb(v);

        for (auto e : g[v]) {
            if (--indeg[e.to] == 0) {
                que.emplace(e.to);
            }
        }
    }

    if (SZ(res) < n) return V<int>{};
    return res;
}

Back to top page