拓扑排序成功当且仅当图无环；Kahn算法本质是BFS环检测+线性序列构造，入度为0才入队因需满足所有前驱已输出，入度统计错误或建图方向颠倒将导致结果非法。
拓扑排序能成功执行，只取决于图是否有环；Kahn 算法本质就是用 BFS 检测环 + 构造线性序列，入度统计只是它的启动条件，不是核心逻辑。
为什么入度为 0 的节点必须先入队？
因为拓扑序要求：所有指向它的边都已被处理（即前驱已输出）。入度 indeg[v] 就是尚未被处理的前驱数量。只有 indeg[v] == 0，才说明 v 的所有依赖都已满足，可以安全加入结果序列。
- 若跳过该检查、盲目选点，可能提前输出有未满足依赖的节点，导致结果非法
- 若图含环，最终队列会变空但仍有节点未输出（
result.size() != n），这是环存在的直接证据 - 多个入度为 0 的节点并存时，顺序不唯一——Kahn 给出的是其中一种合法解，不是“唯一正确答案”
std::queue 与 std::vector 在 Kahn 中的角色分工
队列只负责暂存「当前可调度」的节点，不保存拓扑序本身；结果必须单独用 std::vector 记录。混淆二者会导致顺序错乱或漏节点。
- 错误写法：
while (!q.empty()) { result.push_back(q.front()); ... }—— 看似简洁，但若用std::queue直接存结果，后续无法随机访问或反转，且语义不清 - 正确做法：用
std::queue管生命周期，用std::vector存最终顺序；BFS 过程中每 pop 一个节点，就 append 到 vector - 性能上无差异，但可读性和调试友好性差别很大：vector 支持索引、打印、断点检查；queue 不支持遍历
邻接表构建时常见的索引越界与反向边错误
Kahn 算法依赖「从 u → v 的边」意味着 v 的入度要加 1，但很多人在建图时把方向弄反，或者用 1-based 输入却按 0-based 存储而没修正。
- 输入边
u v表示 u → v，则应执行graph[u].push_back(v)，同时indeg[v]++；若写成indeg[u]++，整个入度统计就全错 - 若题目给的是 1-indexed 节点编号（如节点编号从 1 到 n），而你用
vector，则需统一减 1：存> graph(n) u-1 → v-1，查indeg[v-1] - 忘记初始化
indeg数组为 0，尤其用vector而非裸数组时，容易遗漏(n, 0)
完整可运行的 Kahn 实现（含环检测）
以下代码去掉注释即可编译运行，重点看三处：入度更新位置、队列与结果分离、环检测判断。
#include <vector>
#include <queue>
#include <iostream>
using namespace std;
vector<int> kahnTopo(const vector<vector>>& graph, int n) {
vector<int> indeg(n, 0);
for (int u = 0; u q;
for (int i = 0; i result;
while (!q.empty()) {
int u = q.front(); q.pop();
result.push_back(u);
for (int v : graph[u]) {
indeg[v]--;
if (indeg[v] == 0) q.push(v);
}
}
if ((int)result.size() != n) return {}; // 有环，返回空 vector
return result;
}
</int></vector></int></iostream></queue></vector>
注意：result.size() != n 是唯一可靠的环判定依据；不要依赖 “队列中途为空” 就提前退出——那只是局部无入度节点，不代表全局无解。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
