C++中唯一稳定拓扑排序写法是vector统计入度+queue BFS；需初始化indegree(n,0)和graph(n)，节点编号从0连续；queue保证FIFO语义，避免DFS退化与额外开销；入度减至0时才入队，用res.size()判结束。
直接用 vector<int></int> 统计入度 + queue 做 BFS，是 C++ 里唯一能稳定检测环、不爆栈、结果可复现的拓扑排序写法。DFS 版本在图稍大或含隐式环时容易漏判，不建议用于生产逻辑。
怎么初始化入度数组和邻接表
节点编号必须从 0 开始连续，否则下标越界或漏统计。假设总节点数为 n：
-
vector<int> indegree(n, 0)</int>—— 别用map或动态扩容，纯浪费 -
vector<vector>> graph(n)</vector>—— 每个graph[u]存所有u → v的v - 遍历每条边
[u, v]时立刻执行indegree[v]++和graph[u].push_back(v)
为什么必须用 queue 而不是 stack 或 priority_queue
queue 保证 FIFO，符合“谁先没依赖谁先排”的语义；换成 stack 就退化成 DFS 模拟，失去环检测能力；用 priority_queue 只在需要字典序最小拓扑序时才加，否则徒增 O(log n) 常数开销。
- 初始化队列：只 push 所有
indegree[i] == 0的i - 每次 pop 后，对每个邻接点
v执行if (--indegree[v] == 0) q.push(v)—— 减和判必须原子操作 - 别在循环里调用
q.size()判断是否结束，要用res.size() 做最终环检测
topo_sort 函数返回空 vector 就代表有环
这是 Kahn 算法最实用的副产物：不需要额外 DFS 判环。只要最终 res.size() != n，就说明存在至少一个节点始终无法入队——它被环锁死了。
立即学习“C++免费学习笔记（深入）”；
- 常见错误现象：
queue提前空了但res还没满 —— 直接 return {}，别试图补救 - 不要把 “找不到入度为 0 的起点” 当作图为空，那是环的铁证
- 如果业务要求必须给出部分序（如构建依赖图失败时仍要输出已确定顺序），那就保留
res并显式报错
真正容易被忽略的是入度更新的时机：必须在遍历 graph[u] 过程中实时减 indegree[v]，而不是先收集再批量处理——后者会导致同一轮内多个节点重复入队，破坏拓扑性。
