トポロジカルソート(Topological Sort)
(graph/topological_sort.cpp)

• View this file on GitHub
• Last update: 2026-03-08 22:25:54+09:00

説明

有向グラフのトポロジカル順序を求める。 閉路があるときは空配列を返す。 計算量は $O(N + M)$。

できること

• vector<int> topological_sort(const vector<vector<int>>& g) g のトポロジカル順序を返す。DAG でなければ空配列を返す

使い方

g[v] に v -> to を入れて使う。 順序は DFS の帰りがけ順を反転したものになる。

Verified with

• test/yosupo_topological_sort.test.cpp

Code

vector<int> topological_sort(const vector<vector<int>> &g) {
    int n = g.size();
    vector<int> state(n), ord;
    ord.reserve(n);
    auto dfs = [&](auto &&self, int v) -> bool {
        state[v] = 1;
        for (auto &&to : g[v]) {
            if (state[to] == 1) return false;
            if (state[to] == 0 && !self(self, to)) return false;
        }
        state[v] = 2;
        ord.emplace_back(v);
        return true;
    };
    for (int i = 0; i < n; ++i) {
        if (state[i] == 0 && !dfs(dfs, i)) return {};
    }
    reverse(ord.begin(), ord.end());
    return ord;
}

/**
 * @brief トポロジカルソート(Topological Sort)
 */

#line 1 "graph/topological_sort.cpp"
vector<int> topological_sort(const vector<vector<int>> &g) {
    int n = g.size();
    vector<int> state(n), ord;
    ord.reserve(n);
    auto dfs = [&](auto &&self, int v) -> bool {
        state[v] = 1;
        for (auto &&to : g[v]) {
            if (state[to] == 1) return false;
            if (state[to] == 0 && !self(self, to)) return false;
        }
        state[v] = 2;
        ord.emplace_back(v);
        return true;
    };
    for (int i = 0; i < n; ++i) {
        if (state[i] == 0 && !dfs(dfs, i)) return {};
    }
    reverse(ord.begin(), ord.end());
    return ord;
}

/**
 * @brief トポロジカルソート(Topological Sort)
 */

Back to top page