Kahn算法通过入度数组和BFS实现拓扑排序并自然检测环：初始化indegree为全0，遍历边更新v的入度；BFS中节点入队后加入结果，对其邻居v减入度，仅当indegree[v]==0时入队；最终若结果长度等于节点总数则无环，否则存在环。
拓扑排序不是万能的，它只对有向无环图（DAG）有效；Kahn 算法用入度统计 + BFS 实现，顺便就能检测环——不用额外写逻辑，看结果长度是否等于节点总数就行。
为什么必须显式维护 indegree 数组而不是靠 DFS 模拟
DFS 版本容易栈溢出、状态标记易错（比如漏清 recStack），且无法在中途可靠判断“卡住是因为环还是数据太深”。indegree 数组把“谁可以开始”变成 O(1) 查询，BFS 过程天然可中断、可调试。
-
indegree必须初始化为全 0，尤其注意节点编号可能不连续但你仍得覆盖全部范围（如节点是 1~100，就别只按边里出现的数来 resize） - 建图时每加一条
u → v边，只做indegree[v]++，别写成indegree[u]++ - 不要用
std::map存入度——哈希开销大，还容易因 key 不存在导致访问未初始化值
queue 取节点后更新邻居入度的正确顺序
核心不是“删边”，而是“让下游节点感知依赖已满足”。错误写法是先 push 再减入度，或减完不检查是否归零就跳过。
- 从
queue取出节点u后，立即把它加入result - 遍历
graph[u]中每个v，执行indegree[v]-- - 只有当
indegree[v] == 0时才调用q.push(v)；indegree[v] > 0时不入队，也不报错 - 如果图含孤立点（即
indegree[i] == 0且graph[i]为空），它会在初始化阶段就被入队，否则会漏掉
怎么判断图中存在环而不是单纯没建好图
环检测就藏在最后一步：BFS 结束后比对 result.size() 和总节点数 n。这个判断比任何 DFS 回溯标记都稳，且无需额外空间。
- 若
result.size() == n，说明所有节点都被成功“剥”出来，图是 DAG，result就是合法拓扑序 - 若
result.size() ，说明有节点始终无法入队（因为入度一直 > 0），它们必然落在至少一个环内 - 不需定位具体哪条边成环——Kahn 算法不负责找环边，只负责告诉你“排不了”，这就够了
- 常见误判场景：输入边列表里漏了某个节点（比如节点 5 完全没出现在任何边中），但
indegree数组没为它预留位置 → 它被忽略，导致result.size() 被误认为有环
真正容易被忽略的是节点编号范围和图规模的匹配——哪怕只漏初始化一个孤立节点的 indegree，整个环检测就失效。写完别急着跑样例，先盯一眼 vector 里的 n 是不是真等于你认定的节点总数。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
