トポロジカルソート
(graph/other/topological_sort.hpp)

• View this file on GitHub
• Last update: 2020-08-25 17:20:34+09:00
• Include: #include "graph/other/topological_sort.hpp"

概要

トポロジカルソート.

計算量

$O(E + V)$

使用例

• topological_sort(g) : グラフgをトポロジカルソート.
  • トポロジカルソートが出来ないならvector<int>()を返す.

Verified with

• test/aoj/GRL_4_B.test.cpp

Code

/**
* @brief トポロジカルソート
* @docs docs/graph/other/topological_sort.md
*/

template <typename T>
vector<int> topological_sort(const Graph<T> &g) {
    vector<int> order, color(g.V, 0);
    auto rec = [&](auto &&f, int v) -> bool {
        color[v] = 1;
        for (auto &e : g.mat[v]) {
            if (color[e] == 2) continue;
            if (color[e] == 1) return false;
            if (not f(f, e)) return false;
        }
        order.push_back(v);
        color[v] = 2;
        return true;
    };
    for (int i = 0; i < g.V; ++i)
        if (not color[i] and not rec(rec, i)) return vector<int>();
    reverse(order.begin(), order.end());
    return order;
}

#line 1 "graph/other/topological_sort.hpp"
/**
* @brief トポロジカルソート
* @docs docs/graph/other/topological_sort.md
*/

template <typename T>
vector<int> topological_sort(const Graph<T> &g) {
    vector<int> order, color(g.V, 0);
    auto rec = [&](auto &&f, int v) -> bool {
        color[v] = 1;
        for (auto &e : g.mat[v]) {
            if (color[e] == 2) continue;
            if (color[e] == 1) return false;
            if (not f(f, e)) return false;
        }
        order.push_back(v);
        color[v] = 2;
        return true;
    };
    for (int i = 0; i < g.V; ++i)
        if (not color[i] and not rec(rec, i)) return vector<int>();
    reverse(order.begin(), order.end());
    return order;
}

Back to top page