トポロジカルソート

有向グラフの頂点を、すべての辺 u → v に対して u が v より前になるように並べるアルゴリズム。

DAG（有向非巡回グラフ）の場合に、全頂点の順序を求められる。

特徴

項目	内容
用途	依存関係の処理、DAG上のDP、閉路検出
計算量	O(V+E)
空間計算量	O(V+E)（グラフを含む）

考え方

1. 各頂点の入次数（入ってくる辺の数）を求める。
2. 入次数が0の頂点をキューに追加する。
3. 頂点を取り出し、その頂点から出る辺を削除する。
4. 入次数が0になった頂点をキューに追加する。
5. キューが空になるまで繰り返す。

実装

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> g(n);
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
    }

    auto topological_sort = [&]() -> vector<int> {
        vector<int> deg(n);
        for (int v = 0; v < n; v++) {
            for (int nv : g[v]) deg[nv]++;
        }

        queue<int> q;
        for (int v = 0; v < n; v++) {
            if (deg[v] == 0) q.push(v);
        }

        vector<int> order;
        while (!q.empty()) {
            int v = q.front();
            q.pop();
            order.push_back(v);
            for (int nv : g[v]) {
                if (--deg[nv] == 0) q.push(nv);
            }
        }
        return order;
    };

    auto order = topological_sort();
    if ((int)order.size() != n) {
        cout << -1 << '\n';
        return 0;
    }

    for (int v : order) cout << v << ' ';
    cout << '\n';
}

使用例

auto order = topological_sort();

// 閉路がある場合、全頂点を取り出せない
if ((int)order.size() != n) {
    // 有向閉路が存在する
} else {
    // orderはトポロジカル順序
}

典型的な使い方

DAG上のDP

トポロジカル順に処理すると、各頂点への遷移元を先に処理できる。

例えば、DAGにおける最長パスの長さ（辺数）を求める。

vector<int> dp(n);
for (int v : order) {
    for (int nv : g[v]) {
        dp[nv] = max(dp[nv], dp[v] + 1);
    }
}
int ans = *max_element(dp.begin(), dp.end());

※ order は全頂点を含むトポロジカル順序とする。

注意点

• 入次数0の頂点から順に取り出す。
• reverse(order) は不要。
• order.size() != n なら有向閉路が存在する。
• トポロジカル順序は一意とは限らない。
• 辞書順最小の順序が必要なら、queue の代わりに最小ヒープを使う。

## 関連

- DFS
- DAG
- 強連結成分分解（SCC）
- DAG上のDP