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

• View this file on GitHub
• Last update: 2026-01-21 11:49:22+09:00
• Include: #include "library/graph/topological_sort.hpp"

トポロジカルソート

できること

• DAGをトポロジカルソートする
• 閉路がある場合は空配列を返却

行きがけ/帰りがけの順はこちらを参考

計算量

$O(V+E)$

• V: 頂点数
• E: 辺の数

使い方

vector<int> sorted = topological_sort(G);

Depends on

• 辺 (library/graph/base/edge.hpp)
• グラフ (library/graph/base/graph.hpp)
• 閉路検出 (library/graph/cycle_detect.hpp)

Verified with

• グラフ - トポロジカルソートのテスト (tests/graph.topological_sort.test.cpp)

Code

#pragma once
#include "library/graph/cycle_detect.hpp"
vector<int> topological_sort(const Graph &G) {
    if (cycle_detect(G).size() != 0) return vector<int>();
    int N = G.size();
    vector<int> seen(N, 0), sorted;
    auto dfs = [&](auto &f, int v) -> void {
        seen[v] = 1;
        for (auto &&[from, to, cost, idx] : G[v]) {
            if (!seen[to]) f(f, to);
        }
        sorted.push_back(v);
    };
    for (int i = 0; i < N; ++i) {
        if (!seen[i]) dfs(dfs, i);
    }
    reverse(sorted.begin(), sorted.end());
    return sorted;
}

#line 2 "library/graph/base/edge.hpp"
struct Edge {
    int from, to;
    long long cost;
    int idx;
    Edge(int from, int to, long long cost = 1, int idx = -1)
        : from(from), to(to), cost(cost), idx(idx) {}
};
#line 3 "library/graph/base/graph.hpp"
struct Graph {
    int N;
    vector<vector<Edge>> G;
    int es;
    Graph() = default;
    Graph(int N) : N(N), G(N), es(0) {}
    const vector<Edge> &operator[](int v) const { return G[v]; }
    int size() const { return N; }
    void add(int from, int to, long long cost = 1) {
        G[from].push_back(Edge(from, to, cost, es++));
    }
    void add_both(int from, int to, long long cost = 1) {
        G[from].push_back(Edge(from, to, cost, es));
        G[to].push_back(Edge(to, from, cost, es++));
    }
    void read(int M, int padding = -1, bool weighted = false,
              bool directed = false) {
        for (int i = 0; i < M; i++) {
            int u, v;
            cin >> u >> v;
            u += padding, v += padding;
            long long cost = 1ll;
            if (weighted) cin >> cost;
            if (directed) {
                add(u, v, cost);
            } else {
                add_both(u, v, cost);
            }
        }
    }
};
#line 3 "library/graph/cycle_detect.hpp"
vector<Edge> cycle_detect(const Graph &G, bool directed = true) {
    int N = G.size();
    vector<bool> seen(N), finished(N);
    vector<Edge> history;
    auto dfs = [&](auto &f, int v, const Edge &e) -> int {
        seen[v] = true;
        history.push_back(e);
        for (const auto &ne : G[v]) {
            auto [from, to, cost, idx] = ne;
            if (!directed and to == e.from) continue;
            if (finished[to]) continue;
            if (seen[to] and !finished[to]) {
                history.push_back(ne);
                return to;
            }
            int pos = f(f, to, ne);
            if (pos != -1) return pos;
        }
        finished[v] = true;
        history.pop_back();
        return -1;
    };
    auto restruct = [&](int pos) -> vector<Edge> {
        vector<Edge> cycle;
        while (!history.empty()) {
            const Edge e = history.back();
            cycle.push_back(e);
            history.pop_back();
            if (e.from == pos) break;
        }
        reverse(cycle.begin(), cycle.end());
        return cycle;
    };
    int pos = -1;
    for (int v = 0; v < N and pos == -1; ++v) {
        if (seen[v]) continue;
        history.clear();
        pos = dfs(dfs, v, Edge({-1, -1, -1, -1}));
        if (pos != -1) return restruct(pos);
    }
    return vector<Edge>();
}
#line 3 "library/graph/topological_sort.hpp"
vector<int> topological_sort(const Graph &G) {
    if (cycle_detect(G).size() != 0) return vector<int>();
    int N = G.size();
    vector<int> seen(N, 0), sorted;
    auto dfs = [&](auto &f, int v) -> void {
        seen[v] = 1;
        for (auto &&[from, to, cost, idx] : G[v]) {
            if (!seen[to]) f(f, to);
        }
        sorted.push_back(v);
    };
    for (int i = 0; i < N; ++i) {
        if (!seen[i]) dfs(dfs, i);
    }
    reverse(sorted.begin(), sorted.end());
    return sorted;
}

Back to top page