Kahn算法必须先统计每个节点入度，因为其核心是每次处理入度为0的节点，初始入度决定起点，动态入度判断后续就绪节点；需用vector indegree(n,0)初始化并遍历边更新，仅当indegree[v]==0时才入队以确保语义正确和环可检。
为什么 Kahn 算法必须先统计每个节点的入度
因为 Kahn 的核心逻辑是「每次只处理入度为 0 的节点」，而入度会随着前驱节点被移除而动态变化。不预先统计初始入度，就无法知道谁是起点；不维护当前入度，就无法判断后续哪些节点已就绪。
常见错误是直接遍历邻接表找“没被访问过的点”，这会导致漏掉中间入度归零但未被发现的节点。正确做法是：用 vector<int> indegree(n, 0)</int> 初始化，建图时对每个 edge[u -> v] 执行 indegree[v]++。
queue 里该存什么、什么时候 push
存的是当前可调度的节点索引（比如 int 类型），不是边或权重。只有当某个节点 v 的 indegree[v] == 0 且尚未入队过，才 push。注意：不能在建图后一次性把所有入度为 0 的点全塞进队列再开始 BFS —— 虽然结果可能对，但失去了“逐层释放依赖”的语义，也掩盖了环检测逻辑。
典型写法：
queue<int> q;
for (int i = 0; i < n; ++i) {
if (indegree[i] == 0) q.push(i);
}
怎么可靠检测图中存在环
拓扑序长度小于节点总数，就说明有环。不能只靠队列空了就结束，也不能依赖某次 indegree[v]-- 后是否等于 0 来判断——因为环内节点的入度永远无法减到 0。
实操要点：
- 用一个
count变量记录已加入拓扑序的节点数，每次从队列 pop 一个就++count - BFS 结束后检查
count != n，若成立则存在环，返回空vector或报错 - 不要用
visited[]数组替代入度数组来判环——它无法反映依赖关系断裂状态
邻接表用 vector<vector>></vector> 还是 vector<list>></list>
用 vector<vector>></vector> 更合适。虽然 list 插入快，但 Kahn 中只做只读遍历（对每个出边节点执行 indegree[v]--），且 vector 缓存友好、索引快、内存连续。
小陷阱：
立即学习“C++免费学习笔记（深入）”；
- 如果图稀疏但节点编号不连续（比如 ID 是大整数），别硬套
vector下标，先离散化映射到[0, n) - 重复边会导致同一
v的入度被多次增加，需在建图时去重，或改用set辅助判重 - 若需支持动态加边，
Kahn就不再适用，得换增量式算法
