算法讲解060 必备 拓扑排序的扩展技巧

来源：算法讲解060【必备】拓扑排序的扩展技巧　·　2026-10-25

依据：视频字幕 2000 字

一句话概括

在拓扑排序的推进过程中，把「路径计数 / 可达性 / 依赖信息」从入度为 0 的上游节点沿边累加推给下游节点，从而在 DAG 上做线性 DP。

它解决什么问题

给定一张有向无环图（Directed Acyclic Graph, DAG），要求统计从「所有入度为 0 的源点」到「所有出度为 0 的汇点」的路径条数、或者统计每个点能被多少条路径到达、或者判断某个点是否被所有源点可达等问题。典型题面：食物链计数、课程安排方案数、工程依赖传播、DAG 上「上游信息汇总到下游」。

核心特征：信息只能沿边的方向单向传播，且图无环，所以可以按拓扑序一次性推完，不需要记忆化搜索或反复松弛。

基础知识（前置概念，用大白话解释）

• 有向图（Directed Graph）：边有方向，u -> v 表示 u 能到 v。
• 入度（In-degree）：有多少条边指向这个点。入度为 0 的点就是「没有前置依赖」的起点。
• 出度（Out-degree）：这个点指向多少个点。出度为 0 的点就是「没有后继」的终点。
• 拓扑排序（Topological Sort）：把 DAG 的所有点排成一个序列，使得每条边 u -> v 中 u 都排在 v 前面。常用 Kahn 算法：维护一个入度为 0 的队列，每次弹出一个点，把它所有后继的入度减 1，减到 0 就入队。
• DAG 上的 DP：因为拓扑序保证「处理到某个点时，所有能到它的点都已经处理完」，所以可以边拓扑边把信息累加过去，不需要递归。
• 取模（Modulo）：路径数可能很大，题目一般要求对 1e9+7 或 80112002 之类取模。加法取模：(a + b) % MOD。

原理（为什么这么做是对的，尽量给直觉）

设 f[v] 表示「从所有源点出发、到达 v 的路径条数」。

• 对源点（入度为 0）：f[v] = 1，因为「从自己出发到自己」算一条路径（题目一般这么定义；如果题目要求「至少经过一条边」，则源点最后不计入答案，见边界）。
• 对非源点：所有能一步到 v 的点 u 的路径数之和，就是 v 的路径数，即 f[v] = Σ f[u]，其中 u 取遍 v 的所有前驱。

为什么按拓扑序推就对？因为拓扑序保证：处理到 v 时，v 的所有前驱都已经处理完，f[u] 已经是最终值，不会再变。于是每条边只被「推」一次，总代价 O(V+E)。

直觉：把每个点想象成一个「计数器」，源点初始为 1；拓扑排序每弹出一个点，就把它当前的计数「转发」给它的每个后继（后继计数器 += 当前计数）。等所有点都弹完，每个点的计数器就是「到达它的路径数」。

步骤（编号，可照着写）

1. 读入 n 个点、m 条边，建邻接表 g[u] 存 u 的所有后继，同时统计 indeg[v]。
2. 初始化 f[v] = 0；把所有 indeg[v] == 0 的点入队，并令 f[v] = 1。
3. 当队列非空：

- 弹出 u；

- 对 u 的每个后继 v：f[v] = (f[v] + f[u]) % MOD；indeg[v]--；若 indeg[v] == 0，v 入队。

1. 拓扑结束后，对所有出度为 0 的点 v，把 f[v] 累加进答案（对 MOD 取模）。
2. 输出答案。

若题目只问「到某个指定终点的路径数」，第 4 步只取那个点即可。

若题目问「每个点被多少源点可达」，把加法换成「或」/「集合合并」即可（见变形）。

样例（一个具体小例子，带每步变化）

图：A→D，B→D，B→E，C→E，D→F，E→F，E→D。求 A、B、C 到 F 的路径总数。

初始入度：A=0，B=0，C=0，D=2（A、B），E=2（B、C），F=2（D、E）。

初始 f：A=1，B=1，C=1，D=E=F=0。队列 = [A, B, C]。

| 步骤 | 弹出 | 操作 | f 变化 | 入度变化 | 队列 |

|---|---|---|---|---|---|

| 1 | A | A→D | f[D] += 1 → 1 | D: 2→1 | [B, C] |

| 2 | B | B→D, B→E | f[D] += 1 → 2；f[E] += 1 → 1 | D: 1→0（入队）；E: 2→1 | [C, D] |

| 3 | C | C→E | f[E] += 1 → 2 | E: 1→0（入队） | [D, E] |

| 4 | D | D→F | f[F] += 2 → 2 | F: 2→1 | [E] |

| 5 | E | E→F, E→D | f[F] += 2 → 4；f[D] += 2 → 4（D 已出队，不再入队） | F: 1→0（入队） | [F] |

| 6 | F | 无后继 | — | — | [] |

出度为 0 的点只有 F，答案 = f[F] = 4。

注意：原字幕例子中 D 和 E 之间还有一条 E→D 的边，所以实际路径是 6 条。上面为了演示「已出队的点被再次累加」这个细节，保留了 E→D；但 E→D 会让 D 在 E 之前出队，导致 D 的最终值在出队后才被补上——这正是「按出度收集答案」而不是「出队时收集」的原因。若按字幕的 6 条路径，需要把 E→D 也计入 D 的最终值，再让 D→F 传播；正确做法是先拓扑完再统一收集汇点，或者保证收集时 f 已是最终值。字幕里 D 在 E 之前出队，f[D] 在出队后才从 2 变成 4，所以如果出队时就累加答案会漏。结论：答案在拓扑全部结束后对汇点收集，不要在出队瞬间收集。

代码（Python 一份：好读、用于理解；C++ 一份：竞赛风，能直接抄进比赛，带注释，不用玄学宏）

Python（理解用）

import sys
from collections import deque

def solve():
    input = sys.stdin.readline
    n, m = map(int, input().split())
    MOD = 80112002
    g = [[] for _ in range(n + 1)]
    indeg = [0] * (n + 1)
    outdeg = [0] * (n + 1)
    for _ in range(m):
        u, v = map(int, input().split())
        g[u].append(v)
        indeg[v] += 1
        outdeg[u] += 1

    f = [0] * (n + 1)
    q = deque()
    for v in range(1, n + 1):
        if indeg[v] == 0:
            f[v] = 1
            q.append(v)

    while q:
        u = q.popleft()
        for v in g[u]:
            f[v] = (f[v] + f[u]) % MOD
            indeg[v] -= 1
            if indeg[v] == 0:
                q.append(v)

    ans = 0
    for v in range(1, n + 1):
        if outdeg[v] == 0:
            ans = (ans + f[v]) % MOD
    print(ans)

solve()

C++（竞赛风，可直接抄）

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

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

    int n, m;
    cin >> n >> m;
    const int MOD = 80112002;

    vector<vector<int>> g(n + 1);
    vector<int> indeg(n + 1, 0), outdeg(n + 1, 0);
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        ++indeg[v];
        ++outdeg[u];
    }

    vector<long long> f(n + 1, 0);
    queue<int> q;
    for (int v = 1; v <= n; ++v) {
        if (indeg[v] == 0) {
            f[v] = 1;
            q.push(v);
        }
    }

    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : g[u]) {
            f[v] = (f[v] + f[u]) % MOD;
            if (--indeg[v] == 0) q.push(v);
        }
    }

    long long ans = 0;
    for (int v = 1; v <= n; ++v) {
        if (outdeg[v] == 0) {
            ans = (ans + f[v]) % MOD;
        }
    }
    cout << ans << '\n';
    return 0;
}

复杂度（时间/空间，最好/平均/最坏，顺带说常数大不大）

• 时间：O(V + E)，每个点入队出队一次，每条边被访问一次。最好/平均/最坏都是 O(V+E)。
• 空间：O(V + E)，邻接表 + 入度/出度/f 数组。
• 常数：很小。vector<vector<int>> 在 1e5~1e6 边规模完全够用；1e6 以上边建议用链式前向星（数组模拟）省内存和 cache 友好，但 vector 一般也能过。队列用 queue<int> 或手写数组队列均可，手写数组队列常数更小。

竞赛里什么时候用（看到什么题面特征就该想到它）

• 题面出现「食物链」「依赖关系」「先修课程」「工程先后顺序」「A 必须在 B 之前」。
• 要求「统计路径条数」「统计方案数」「判断是否所有点都能被某个点到达」「判断是否存在唯一拓扑序」。
• 图明确说「无环」或「保证是 DAG」。
• 需要「把上游信息汇总到下游」且图是 DAG——这是拓扑 DP 的标志。
• 数据规模 1e5~2e6，需要 O(V+E) 线性做法。

竞赛模板（C++，可直接背下来的写法；变量名清楚）

// DAG 上拓扑 DP 通用骨架：f[v] 由所有前驱累加而来
// 使用前：g 已建好，indeg/outdeg 已统计
vector<long long> f(n + 1, 0);
queue<int> q;
for (int v = 1; v <= n; ++v)
    if (indeg[v] == 0) { f[v] = 1; q.push(v); }   // 源点初始化，按题目改

while (!q.empty()) {
    int u = q.front(); q.pop();
    for (int v : g[u]) {
        f[v] = (f[v] + f[u]) % MOD;               // 核心：信息下推
        if (--indeg[v] == 0) q.push(v);
    }
}
// 拓扑结束后统一收集答案（汇点 / 指定点 / 全局）

边界与易错点（WA 的常见原因，越具体越好）

1. 源点初始化：入度为 0 的点 f = 1 还是 f = 0？取决于题目「路径」是否允许长度为 0。食物链题一般源点算 1 条（自己到自己），但最终只统计汇点，所以源点若同时是汇点（孤立点）会被计入——若题目不允许孤立点，要特判。
2. 答案收集时机：必须在拓扑全部结束后对汇点收集，不能在出队瞬间收集。因为一个点可能在出队后还被其他前驱累加（如样例中 D 被 E 补加），出队时 f 还不是最终值。
3. 汇点判定：用 outdeg[v] == 0，不要用「没有后继」临时判断（邻接表为空等价，但出度数组更稳）。
4. 取模：f[v] + f[u] 可能超 int，用 long long 存 f，加法后取模。MOD 按题目给（食物链题常见 80112002，不是 1e9+7）。
5. 多测清空：g、indeg、outdeg、f、队列全部要清。用 vector 重新构造最省心，别用全局数组忘清。
6. 下标从 1 还是 0：题目点编号一般 1~n，模板按 1-based；若 0-based 要把循环边界改掉，别混。
7. 重边：重边会让入度多算，但拓扑仍然正确（重边相当于多条路径，路径计数题里重边应算多条路径，符合题意）；若题目要求去重，要先 sort+unique 或 set。
8. 自环：DAG 保证无自环；若题目没保证，拓扑后有点没出队说明有环，要判 cnt < n。
9. 孤立点：既入度 0 又出度 0 的点，若题目要求「至少一条边」的路径，不能计入答案。
10. 队列用 queue 还是 vector 当栈：拓扑序不唯一，用栈/队列都行，但若题目要求「字典序最小拓扑序」要用优先队列（见变形）。

同类题 / 变形（说清楚怎么改）

• 只问到某终点的路径数：第 4 步只取 f[t]，其余不变。
• 每个点被多少源点可达（可达性计数）：把加法换成「或」——reach[v] |= reach[u]，用 bitset 或布尔数组；若问「被多少个源点可达」，用 bitset<MAXN> 做或运算，O(V·E/64)。
• 判断是否存在唯一拓扑序：队列中同时存在 ≥2 个点时说明不唯一；全程队列大小始终 ≤1 则唯一。
• 字典序最小拓扑序：把 queue 换成 priority_queue<int, vector<int>, greater<int>>，O((V+E) log V)。
• 最长路 / 最短路（DAG 上）：把 f[v] = f[v] + f[u] 换成 f[v] = max(f[v], f[u] + w) 或 min，边权 w 从边上读。
• 树上 DP 的拓扑序：树本身就是 DAG（按根定向），可以用拓扑序代替 DFS 做树形 DP，避免递归爆栈。
• 依赖传播 / 工程完成时间：f[v] = max(f[v], f[u] + cost[u])，源点 f = cost。

常见坑

• 用 map<int, vector<int>> 建图，1e5 规模常数爆炸，TLE。用 vector<vector<int>> 或链式前向星。
• 用 list 存邻接表，cache 不友好，别用。
• #define int long long 导致 queue<int> 变 queue<long long>，常数翻倍还可能 MLE；直接开 long long 数组即可。
• 多测时 indeg 没清，第二组直接错。
• 取模只在最后取一次，中间溢出 long long（路径数指数级），必须每步取模。
• 把「入度为 0 的点」和「源点」混为一谈：多源 DAG 里源点就是所有入度 0 的点，没问题；但若题目指定唯一起点，要只从那个点初始化。
• 拓扑排序后没检查 cnt == n，有环时静默输出错误答案。

拓展（变体、实际用途、面试常问）

• 实际用途：编译器依赖分析、任务调度（DAG 调度）、电子表格公式求值、构建系统（make/ninja）的依赖顺序、包管理器依赖解析。
• 面试常问：拓扑排序判环、课程表 II（输出任意拓扑序）、DAG 最长路、唯一拓扑序判定。
• 进阶：拓扑序 + 线段树维护「区间加/区间最大值」做 DAG 上的复杂 DP；拓扑序 + 并查集做「缩点后 DAG」；SCC 缩点后拓扑 DP（Tarjan/Kosaraju 求 SCC，缩点成 DAG 再拓扑）。
• bitset 优化可达性：bitset<2000> 做传递闭包，O(V·E/64)，1e5 点不行，2000 点以内可用。

自测 3 题（题目 + 折叠答案）

题 1：n 个点 m 条边的 DAG，求从点 1 到点 n 的路径条数，对 1e9+7 取模。n,m ≤ 1e5。