拓扑排序 (Topological Sort)¶

拓扑排序（Topological Sort）是将有向无环图 (DAG - Directed Acyclic Graph) 中的所有顶点排成一个线性序列，使得图中任意一条有向边 \((u, v)\)，\(u\) 在序列中均出现在 \(v\) 的前面。

若图中有环，则无法构成拓扑序列。因此拓扑排序也是检验有向图是否存在环的经典手段。

1. Kahn 算法 (基于入度与 BFS)¶

核心逻辑：

统计所有节点的初始入度（\(\text{in\_degree}\)）。
将所有入度为 \(0\) 的节点加入队列。
队首出队加入拓扑序列，遍历其所有出边 \((u, v)\)，将 \(v\) 的入度减 \(1\)。若 \(v\) 的入度减为 \(0\)，则将 \(v\) 入队。
若最终拓扑序列包含的节点数等于总节点数 \(n\)，则排序成功；否则说明图中存在有向环。

时间复杂度：\(\mathcal{O}(V + E)\)，空间复杂度：\(\mathcal{O}(V + E)\)。

#include <vector>
#include <queue>

// 返回拓扑排序序列 (0-indexed)。若图中含环，返回空 vector
std::vector<int> topological_sort(int n, const std::vector<std::vector<int>> &adj) {
    std::vector<int> in_degree(n, 0);
    for (int u = 0; u < n; ++u) {
        for (int v : adj[u]) {
            in_degree[v]++;
        }
    }

    std::queue<int> q;
    for (int i = 0; i < n; ++i) {
        if (in_degree[i] == 0) {
            q.push(i);
        }
    }

    std::vector<int> topo;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        topo.push_back(u);

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

    if ((int)topo.size() != n) {
        return {}; // 存在有向环
    }
    return topo;
}

2. 字典序最小的拓扑排序¶

当题目要求输出字典序最小的拓扑排序时，只需将 Kahn 算法中的标准队列替换为小顶堆（优先队列）即可。

时间复杂度：\(\mathcal{O}(V \log V + E)\)。

std::vector<int> lexicographical_topological_sort(int n, const std::vector<std::vector<int>> &adj) {
    std::vector<int> in_degree(n, 0);
    for (int u = 0; u < n; ++u) {
        for (int v : adj[u]) in_degree[v]++;
    }

    // 小顶堆，每次出队当前编号最小的可选节点
    std::priority_queue<int, std::vector<int>, std::greater<int>> pq;
    for (int i = 0; i < n; ++i) {
        if (in_degree[i] == 0) pq.push(i);
    }

    std::vector<int> topo;
    while (!pq.empty()) {
        int u = pq.top();
        pq.pop();
        topo.push_back(u);

        for (int v : adj[u]) {
            if (--in_degree[v] == 0) pq.push(v);
        }
    }

    if ((int)topo.size() != n) return {};
    return topo;
}

经典推荐习题¶

CSES 1679 - Course Schedule

提示

Kahn 算法或基于 DFS 拓扑排序的教科书式模板题。若图中存在有向环则输出 IMPOSSIBLE；否则输出任意合法的拓扑序列。
CSES 1680 - Longest Flight Route

提示

求 DAG 上从 1 到 \(n\) 的最长路。先对图进行拓扑排序，或按拓扑序进行动态规划：\(dp[v] = \max_{(u, v) \in E} (dp[u] + 1)\)，初始状态 \(dp[1] = 1\)，其余 \(dp[i] = -\infty\)。记录前驱转移节点即可复原最优航线。
POI 2014 - Rally (raj)
提示

在 DAG 中删除恰好一个点，使得剩余子图的最长路最小（极小化极大值）。
- 沿拓扑序进行 DP，分别求出以 \(u\) 结尾的最长路 \(f[u]\) 与以 \(u\) 开头的最长路 \(g[u]\)。
- 当拓扑序第 \(i\) 个点 \(v\) 被删除时，剩余图中的任意路径只有三种可能：
  1. 完全处于点 \(v\) 之前（由 \(f\) 的前缀最大值限制）；
  2. 完全处于点 \(v\) 之后（由 \(g\) 的后缀最大值限制）；
  3. “跨过”点 \(v\) 的边 \(x \to y\)（满足 \(pos(x) < i < pos(y)\)），此时该跨越路径长度为 \(f[x] + 1 + g[y]\)。
- 沿拓扑序扫描各点，利用线段树维护跨越边的最大值，每次可在 \(\mathcal{O}(\log N)\) 时间内查询，总体时间复杂度为 \(\mathcal{O}((N + M) \log N)\)。
POI 2015 - Zadanie Pustynia (pus)
提示

差分约束转化为 DAG：每个限制形如在区间 \([l, r]\) 内选定的若干位置的值严格大于其余未选定位置的值，即对任意未选位置 \(y\) 与选定位置 \(x\)，满足 \(val[x] \ge val[y] + 1\)。
- 暴力连边会导致 \(\mathcal{O}(K \cdot len)\) 条边（引发 TLE/MLE）。
- 在序列 \([1, N]\) 上建立线段树辅助建图：未被选中的区间可拆分为 \(\mathcal{O}(K \log N)\) 个线段树节点。
- 为每个限制建立一个虚拟汇点 \(P\)：从线段树对应未选节点向 \(P\) 连权值为 0 的有向边，再从 \(P\) 向每个选中的位置 \(x\) 连权值为 1 的有向边。
- 由于所有边权 \(\ge 0\) 且要求判定无环并求出各点下界值，在建出的 DAG 上直接运行 Kahn 拓扑排序算法，在 \(\mathcal{O}(N + \sum K \log N)\) 时间内求出答案。若检测到环或数值超过 \(10^9\) 则输出 NIE。

LeetCode 经典真题精选与题解提示¶

LeetCode 207 - 课程表 (Course Schedule) 中等
提示

有向图判环基石。
- 根据先修课程对 \([u, v]\)（即 \(v \to u\)）建有向图，统计所有节点入度。
- 将所有入度为 0 的节点推入队列执行 Kahn 算法。最终若出队节点数等于课程总数，说明图为 DAG 且无环，可以学完；反之存在有向环。
LeetCode 210 - 课程表 II (Course Schedule II) 中等
提示

拓扑序列构造。
- 在 Kahn 算法的 BFS 过程中，按节点出队顺序依次记录节点编号。
- 若最终出队节点数等于 \(n\) 则返回记录的序列；若小于 \(n\) 说明存在环，返回空数组。
LeetCode 269 - 火星词典 (Alien Dictionary) 困难
提示

字典序偏序建图与拓扑排序。
- 比较词典中每对相邻字符串 \(w_i\) 和 \(w_{i+1}\)：找到第一个不同的字符对 \(c_1 \ne c_2\)，建立一条从 \(c_1\) 指向 \(c_2\) 的有向边。特别注意：若 \(w_{i+1}\) 是 \(w_i\) 的真前缀，则属于非法输入，直接判定无解。
- 在建成的字符图上运行拓扑排序（Kahn 或 DFS 三色标记判环），若存在环则无合法顺序，否则输出字符拓扑序列。
LeetCode 1857 - 有向图中最大颜色值 (Largest Color Value in a Directed Graph) 困难
提示

拓扑排序 + DAG 路径动态规划。
- 设 \(dp[u][c]\) 表示以节点 \(u\) 结尾的有效路径中，颜色 \(c\)（\(0 \le c < 26\)）出现的最大频次。
- 在 Kahn 算法遍历 DAG 的过程中，当处理边 \(u \to v\) 时，状态转移为 \(dp[v][c] = \max(dp[v][c], dp[u][c])\)。
- 节点 \(u\) 出队处理时将其自身颜色 \(dp[u][colors[u]]++\) 并更新全局最大值。若最终拓扑遍历节点数小于 \(n\) 则说明有环，返回 \(-1\)。
LeetCode 1203 - 项目管理 (Sort Items by Groups Respecting Dependencies) 困难
提示

双层拓扑排序 (分层拓扑)。
- 对未分配小组的项目（\(group[i] = -1\)），为其分配全局唯一的虚拟组号，确保每个项目严格属于一个组。
- 建立两张图：组间依赖图（只在跨组依赖时连边）和组内项目依赖图（同组内部依赖连边）。
- 分别对“所有组”执行组间拓扑排序，以及对“各组内部的项目”执行组内拓扑排序。若任意一层拓扑排序检测到环，则无解返回空数组。最后按照合法的组拓扑顺序拼接各个组内已排好序的项目列表即可。