拓扑排序前必须检查图是否有环，Kahn算法通过比较输出顶点数与总顶点数判断环：若不等则存在环；需用std::vector维护入度数组和邻接表，边方向为v→u，核心循环仅取、删、更新，初始化须覆盖所有顶点。
拓扑排序前必须检查图是否有环
拓扑排序只对有向无环图（DAG）有效，Kahn 算法本身能顺便检测环——如果最终输出的顶点数少于图中总顶点数，说明存在环。indegree[v] 为 0 才入队，若某轮没新节点入队但还有未访问节点，就卡住了，环已实锤。别跳过这步验证，否则结果无效。
std::queue 和 std::vector 是最简可行组合
不需要手写链表或用 std::deque，std::queue（默认基于 std::deque）足够；入度数组用 std::vector，索引即顶点编号（假设顶点编号为 0 到 n-1）。邻接表用 std::vector<:vector>>，比 std::map 更快且内存连续。
常见错误：把边方向搞反。Kahn 要求存的是「v → u」时，在邻接表中记录 adj[v].push_back(u)，并在统计入度时做 indegree[u]++。方向错，入度全乱。
核心循环里只做三件事：取、删、更新
每次从队列取一个入度为 0 的节点 v，加入结果序列；遍历所有 v 的直接后继 u；对每个 u 执行 indegree[u]--，若减到 0 就入队。没有额外判断、不重排、不回溯。
- 不要在循环中修改
adj[v]或清空邻接表——边关系是只读的 - 不要用
std::set或排序保证字典序——Kahn 本身不保序，如需字典序最小解，改用std::priority_queue替代std::queue - 入度数组初始化必须覆盖全部顶点，哪怕某顶点无边出入，也要显式设为 0
完整可运行片段（无依赖，C++11 起可用）
#include <vector>
#include <queue>
#include <iostream>
std::vector<int> kahnTopo(const std::vector<:vector>>& adj, int n) {
std::vector<int> indegree(n, 0);
for (int v = 0; v q;
for (int v = 0; v result;
while (!q.empty()) {
int v = q.front(); q.pop();
result.push_back(v);
for (int u : adj[v]) {
if (--indegree[u] == 0) {
q.push(u);
}
}
}
if ((int)result.size() != n) {
return {}; // 有环，返回空 vector
}
return result;
}
</int></:vector></int></iostream></queue></vector>
注意：返回空 std::vector 表示环存在，调用方必须检查大小；顶点数 n 必须准确传入，不能靠 adj.size() 推断——孤立点不会出现在任何 adj[v] 中，但仍是图的一部分。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
