kahn算法必须先统计每个节点入度，因为入度为0是识别无前置依赖节点的唯一可靠判据；未预先统计或漏更新会导致重复入队、跳过节点或死循环。
为什么 Kahn 算法必须先统计每个节点的入度
因为 Kahn 算法的本质是「每次剥离没有前置依赖的节点」，而入度为 0 就是这个条件的唯一可靠判据。不预先统计或中途漏更新入度，会导致节点被重复加入队列、跳过合法节点，甚至死循环——比如图中存在环时，剩余节点入度永远 > 0，队列会提前为空但未遍历完所有节点。
实际编码中常见错误是：只在建图时初始化入度数组，后续对邻接节点的入度减操作写成 indeg[v]-- 却忘了检查 v 是否越界；或者用 map<int int></int> 存入度但没覆盖所有节点（比如某节点只出不入，未显式初始化为 0）。
- 推荐统一用
vector<int></int>，大小设为节点总数n，索引即节点 ID（假设节点编号为0到n-1） - 若节点编号稀疏（如
1, 100, 1000），改用unordered_map<int int></int>，但建图后需对所有出现过的节点显式补零 - 入度数组必须在 BFS 开始前完成最终值，不能边遍历边补统计
如何用 BFS 正确实现 Kahn 的节点剥离逻辑
BFS 在这里不是为了找最短路径，而是保证「拓扑序的合法性」：只有当某节点所有前驱都已被输出，它才可进入队列。队列里存的永远是当前可调度的节点集合。
关键动作只有三步：取队首、输出、遍历其后继并更新入度。漏掉任一后继的 indeg[neighbor]--，就会导致该后继永远卡在队列外。
- 初始化：把所有
indeg[i] == 0的i入队（注意是全部，不是只入一个） - 循环中：对每个出队节点
u，遍历graph[u]中每个v，执行indeg[v]--；若减后为0，立即push(v) - 不要在入队时检查环——环的检测靠最终结果长度是否等于节点总数
queue<int> q;
for (int i = 0; i vector<int> topo;
while (!q.empty()) {
int u = q.front(); q.pop();
topo.push_back(u);
for (int v : graph[u]) {
indeg[v]--;
if (indeg[v] == 0) q.push(v);
}
}
if (topo.size() != n) /<em> 存在环 </em>/;</int></int>
图的存储方式对 Kahn 实现的影响
邻接表是最自然的选择，但具体结构会影响代码清晰度和边界处理。用 vector<vector>></vector> 最直接；若用 vector<list>></list> 或 vector<set>></set>，只是遍历语法稍异，逻辑不变。但要注意：
- 若用
vector<unordered_set>></unordered_set>去重边，得确保建图时调用insert()而非push_back()，否则重复边会让入度被多减 - 邻接矩阵（
vector<vector>></vector>）理论上可行，但遍历每行找true是O(n)，整体退化为O(n²)，不推荐 - 如果输入是边列表（
vector<pair>></pair>），务必先转邻接表 + 统计入度，不要在 BFS 循环里反复扫描边列表
环检测与结果验证不能只看队列是否为空
队列空了只说明「当前没有入度为 0 的节点」，不等于图已处理完。真正可靠的环判断依据是：拓扑序列长度是否等于总节点数。
容易忽略的点是节点编号不连续或含孤立点。例如图有 5 个节点，但只给了 3 条边，且节点 2 完全孤立——它入度为 0，必须被纳入初始队列，否则 topo.size() 会是 4 而非 5，误报为环。
- 务必以「所有可能的节点 ID 集合」为基准计算
n，而不是仅从边中提取最大编号 - 若输入未明确节点总数，需先扫描所有边，收集全部出现的节点，再取
set.size()作为n - 调试时可打印每个节点最终入度值，非零值节点就是环上成员（或环可达节点）
拓扑排序本身不难，难的是把入度维护、节点覆盖、环判定这三件事在一次 BFS 中严丝合缝地串起来——少一次 indeg[v]--，或多一次未初始化，结果就不可信。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
