核心逻辑与数学原理
拓扑排序（Topological Sort）是一种对有向无环图（Directed Acyclic Graph, DAG）顶点进行线性排序的算法。排序后，对于图中的任意一条有向边 $(u, v)$，顶点 $u$ 必然在排序中出现在顶点 $v$ 的前面。
在 NOIP 体系下，拓扑排序的核心代数原理与状态控制包含以下三个要素：
1. 入度驱动范式：Kahn 算法（广度优先搜索变形）
Kahn 算法的本质是基于消除零入度节点的动态拓扑收敛。
- 物理意义：一个顶点的入度（In-degree）代表该任务当前必须依赖的前置条件数量。入度为 $0$ 的节点意味着它没有任何前置依赖，可以立即执行。
- 动力学过程：算法维护一个零入度状态集（队列）。每次从集中提取一个顶点 $u$ 加入拓扑序列，并“逻辑删除”以 $u$ 为起点的所有出边 $(u, v)$。这会导致其后续邻接点 $v$ 的入度减 1（$ ext{in ext{_}degree}[v] ightarrow ext{in ext{_}degree}[v] - 1$）。若减完后 $v$ 的入度也降为 $0$，说明其前置条件已全部备齐，无缝并入零入度集中。
- 时间复杂度：每个顶点入队一次，每条边被扫描一次，复杂度严格为 $O(V + E)$。
2. 环路判定的拓扑判据
如果图中存在有向环路（如 $A o B o C o A$），环内所有节点的入度在外界松弛耗尽后，永远无法降为 $0$。因此，它们绝对不可能进入零入度队列。
- 无解拓扑判据：当队列变空、算法终止时，若最终拓扑序列中包含的顶点数量严格小于原图的总顶点数 $N$（$ ext{cnt} < N$），则在数学上判定该图存在有向环，无法完成拓扑排序。
3. 全局字典序最小的拓扑链选择
在许多竞赛实际场景中，满足拓扑关系的位置往往不唯一。若题目强制要求输出全局字典序最小的拓扑序列，传统的 FIFO 队列（std::queue）将无法胜任。
- 优化原理：必须将零入度集的数据结构无缝切换为小根堆（优先队列，
std::priority_queue）。每次当有多个节点同时满足入度为 $0$ 时，堆结构能确保当前编号最小的节点优先出队，从而贪心构建出全局字典序最小的合法拓扑链。
算法推导与状态设计
1. Kahn 算法状态设计
定义一维计数数组 in_degree[i]，在读入边 $(u, v)$ 时同步执行：in_degree[v]++。
- 初始化：扫描整个图，将所有满足
in_degree[i] == 0的节点压入优先队列中。 - 状态转移方程： 对于当前出堆的零入度节点 $u$，遍历其邻接表中的出边。对于每个终点 $v$：
$$ ext{in ext{_}degree}[v] ightarrow ext{in ext{_}degree}[v] - 1$$
$$ ext{if } ( ext{in ext{_}degree}[v] == 0) ext{ pq.push}(v)$$
C++ 标准源码（全局字典序最小拓扑排序模板）
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
const int MAXN = 100005;
std::vector<int> adj[MAXN]; // 邻接表存储有向图
int in_degree[MAXN]; // 记录每个节点的入度
std::vector<int> topo_res; // 存储最终生成的拓扑序列
bool topological_sort(int n) {
// 核心战术：使用小根堆确保当前所有入度为 0 的节点中，编号最小的优先出队
std::priority_queue<int, std::vector<int>, std::greater<int>> pq;
// 1. 全局扫描，将初始入度为 0 的点并入状态堆
for (int i = 1; i <= n; ++i) {
if (in_degree[i] == 0) {
pq.push(i);
}
}
// 2. 拓扑迭代扩张
while (!pq.empty()) {
int u = pq.top();
pq.pop();
topo_res.push_back(u); // 归并入最终拓扑序列
// 遍历以 u 为起点的所有出边
for (size_t i = 0; i < adj[u].size(); ++i) {
int v = adj[u][i];
in_degree[v]--; // 逻辑切断边 $(u, v)$，终点入度减 1
// 必须严格判定 == 0 的瞬间
if (in_degree[v] == 0) {
pq.push(v);
}
}
}
// 3. 环路判定代数校验
// 若最终生成的序列点数不等于总点数，说明图中有向图存在环路，拓扑链断裂
return topo_res.size() == static_cast<size_t>(n);
}
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
int n, m;
if (!(std::cin >> n >> m)) return 0;
for (int i = 0; i < m; ++i) {
int u, v;
std::cin >> u >> v;
adj[u].push_back(v); // 建立有向边 u -> v
in_degree[v]++; // 终点 v 添加入度
}
if (!topological_sort(n)) {
std::cout << -1 << "\n"; // 图中包含有向环，拓扑排序失败
} else {
for (int i = 0; i < n; ++i) {
std::cout << topo_res[i] << (i == n - 1 ? "" : " ");
}
std::cout << "\n";
}
return 0;
}NOIP 实战避坑指南
- 混淆“字典序最小的拓扑序”与“反向拓扑序”：
这是竞赛题中极其经典的一个大坑。有些题目要求“让编号小的节点尽量靠前”，这在字面直觉上很容易让人觉得直接用小根堆跑 Kahn 算法就行。但实际上，“字典序最小”和“让小编号尽量靠前”在数学上是不等价的（例如：序列 $[1, 4, 2, 3]$ 的字典序小于 $[2, 1, 3, 4]$，但是后者的
1更加靠前）。
- 战术修正：如果题目要求让编号小的点尽量靠前，正确的做法是建反向图，然后用大根堆跑拓扑排序，最后将得到的序列逆序输出。
- 入度减 1 的条件拦截写错：
在松弛邻接点时，判断语句必须严格写成
if (in_degree[v] == 0)。如果贪图省事写成if (in_degree[v] <= 0)，虽然在绝大多数正常图上没有区别，但如果原图由于某种建图变形导致初始包含了入度为负数（错误状态）或者发生并发逻辑，由于重复压入堆结构会造成算法出现逻辑漏洞。
经典 NOIP/洛谷 真题
1. 洛谷 P1347 排序
- 题意描述：
给定 $N$ 个大写字母以及 $M$ 个形如
A<B的关系，要求输出字母的排序。
2. Kahn P4017
- 题意描述：
给定 $N$ 个形如
A<B的关系，判断是否存在环路，并输出拓扑排序结果。