拓扑排序

一句话算法

拓扑排序就是不断删除入度为 0 的点：谁已经没有前置依赖，谁就可以进入答案序列。

问题模型

给定一张有向图 $G=(V,E)$，边 $u\to v$ 表示：

• $u$ 必须排在 $v$ 前面；
• 或者任务 $v$ 依赖任务 $u$；
• 或者状态 $v$ 只能在 $u$ 之后被处理。

拓扑排序要输出一个点序列，使得每条边 $u\to v$ 都满足 $u$ 在 $v$ 前面。

核心直觉

把有向边看成“前置课程”。

一个点的入度表示还有多少个前置任务没完成。入度为 0 的点没有任何前置依赖，可以立刻安排。安排完这个点以后，它指向的后继点少了一个前置依赖，于是后继点的入度减一。

如果整个过程最后还有点没有被安排，说明剩下的点互相依赖，它们组成了有向环。

算法步骤

Kahn 算法的流程：

1. 统计每个点的入度 indeg[v]。
2. 把所有入度为 0 的点放入队列。
3. 当队列非空：
   • 取出队首点 u，加入拓扑序；
   • 枚举所有边 u -> v；
   • 将 indeg[v]--；
   • 如果 indeg[v] == 0，把 v 放入队列。
4. 如果最终拓扑序长度等于 $n$，说明排序成功。
5. 如果拓扑序长度小于 $n$，说明图中存在有向环。

字典序最小拓扑序

如果题目要求输出字典序最小的拓扑序，把普通队列换成小根堆即可。

理由很简单：任何时刻所有入度为 0 的点都没有未完成前驱，它们之间可以任选一个先输出。为了让序列字典序最小，每一步都选编号最小的可选点。

算法证明

关键不变量： 队列中的点，恰好是当前还未输出、且所有前驱都已经输出的点。

1. 初始化正确

   初始入度为 0 的点没有任何前驱，显然可以作为拓扑序开头。

2. 删除一个点后不变量仍成立

   输出点 u 后，相当于从图中删除 u 和它的所有出边。对于每条边 u -> v，v 少了一个未完成前驱，所以 indeg[v]--。

   当 indeg[v] 变成 0，表示 v 的所有前驱都已经被删除，也就是都已经输出，因此 v 可以进入队列。

3. 输出序列合法

   对任意边 $u\to v$，v 只有在所有前驱输出后才可能入队，所以 $u$ 一定在 $v$ 前面输出。

4. 环检测正确

   如果图中有环，环上每个点至少有一个来自环内的前驱。只要环内点都没被删除，它们的入度就不会变成 0，因此无法全部输出。

   反过来，如果算法结束时还有点没输出，剩余子图中没有入度为 0 的点。从任一点不断沿入边往前走，因为点数有限，必然重复某个点，形成有向环。

所以，Kahn 算法能正确输出 DAG 的拓扑序，并能判断有向环是否存在。

复杂度分析

设点数为 $n$，边数为 $m$。

• 普通队列版：每个点入队出队一次，每条边被扫描一次，时间复杂度 $O(n+m)$。
• 空间复杂度 $O(n+m)$。
• 若使用小根堆求字典序最小拓扑序，时间复杂度为 $O((n+m)\log n)$。

代码实现

下面模板读入 n m 和 m 条有向边 u v，输出一个拓扑序；如果存在环，输出 Cycle。

        
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66

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

struct TopologicalSort {
    int n;
    vector<vector<int>> graph;
    vector<int> indeg;

    explicit TopologicalSort(int n) : n(n), graph(n + 1), indeg(n + 1, 0) {}

    void add_edge(int u, int v) {
        graph[u].push_back(v);
        indeg[v]++;
    }

    vector<int> kahn() {
        queue<int> q;
        vector<int> deg = indeg;
        vector<int> order;

        for (int i = 1; i <= n; i++) {
            if (deg[i] == 0) q.push(i);
        }

        while (!q.empty()) {
            int u = q.front();
            q.pop();
            order.push_back(u);

            for (int v : graph[u]) {
                deg[v]--;
                if (deg[v] == 0) q.push(v);
            }
        }

        return order;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    TopologicalSort solver(n);
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        solver.add_edge(u, v);
    }

    vector<int> order = solver.kahn();
    if ((int)order.size() != n) {
        cout << "Cycle\n";
        return 0;
    }

    for (int i = 0; i < n; i++) {
        if (i) cout << ' ';
        cout << order[i];
    }
    cout << '\n';
    return 0;
}
    

测试用例

输入：

5 5
1 3
2 3
3 4
2 5
5 4

输出：

1 2 3 5 4

解释：

• 3 必须在 1,2 之后；
• 5 必须在 2 之后；
• 4 必须在 3,5 之后。

输出序列满足所有边的先后限制。

有环样例：

3 3
1 2
2 3
3 1

输出：

Cycle

应用分类详解

拓扑排序的本质是处理“有向依赖关系”。只要题目里出现先后限制、依赖顺序、DAG 上转移，就应该想到拓扑排序。

一、任务依赖与课程安排

典型模式： 若干任务之间有前置依赖，要求给出一种合法执行顺序。

识别信号： “必须先完成 A 才能做 B”“课程先修关系”“工程任务排程”。

核心建模： 任务是点，前置关系 A -> B 是边，拓扑序就是合法执行顺序。

二、DAG 动态规划

典型模式： 图是 DAG，需要按依赖方向做 DP。

识别信号： “有向无环图”“路径计数”“最长路径”“状态只能从前驱转移”。

核心建模： 先求拓扑序，再按拓扑序处理点，保证计算一个点时它的所有前驱已经算完。

三、唯一拓扑序与环检测

典型模式： 不只要一个拓扑序，还要判断顺序是否唯一，或是否存在矛盾。

识别信号： “排名是否确定”“关系是否矛盾”“能否唯一确定顺序”。

核心建模： Kahn 算法过程中，如果某一时刻可选入度 0 点超过一个，拓扑序不唯一；如果最后没有输出所有点，则有环。

四、字典序最小/最大拓扑序

典型模式： 合法拓扑序可能有很多个，题目要求最小字典序或最大字典序。

识别信号： “若有多种方案，输出字典序最小”“编号小的优先”。

核心建模： 把队列换成优先队列。最小字典序用小根堆；某些反向建图题可以通过反向拓扑序处理最大字典序。

经典例题

1. luogu-P1113

任务调度与最早完成时间。先按依赖关系建 DAG，再在拓扑序上做 DP：一个任务的最早开始时间由所有前驱任务的完成时间取最大值。

2. luogu-P1347

判断排序关系。每加入一条大小关系后做拓扑排序：若存在环则矛盾，若每一步只有一个可选点则当前顺序唯一。

3. luogu-P4017

最大食物链计数。把食物链方向建成 DAG，从入度为 0 的点开始按拓扑序转移路径数量。

4. luogu-P1983

车站分级。题目给出的停靠关系可以转成等级依赖，依赖图上的最长层数就是最少等级数。

参考

• Kahn 算法
• DAG 动态规划