Kahn算法用std::queue和入度数组实现拓扑排序：建邻接表vector、初始化indeg数组，入度0节点入队；每次出队时遍历邻接点并减其入度，为0则入队；若队空但未输出全部节点，则有环。
怎么用 std::queue 和入度数组做拓扑排序
拓扑排序本质是按依赖关系线性化有向无环图（DAG），C++里最稳的实现就是「Kahn 算法」：统计每个节点入度，把入度为 0 的扔进 std::queue，逐个取出并减少邻居入度。
关键不是“能不能写”，而是别漏掉三个动作：
- 建图时用
vector<vector>></vector>存邻接表，别用map或set—— 没必要，还慢 - 入度数组大小必须和节点编号范围对齐，比如节点是 0~n-1，就开
vector<int> indeg(n)</int>；要是节点编号稀疏（比如 1、5、100），得先离散化或用unordered_map管理入度 - 每次从队列取节点后，要遍历它的所有邻接点，并对每个邻接点执行
indeg[v]--；只有当indeg[v] == 0时才入队 —— 少判这一句，结果就漏节点
遇到 std::queue 为空但还有节点没输出，说明图有环
这是 Kahn 算法自带的环检测能力。只要最终输出的节点数
常见误判场景：
立即学习“C++免费学习笔记（深入）”；
- 输入边时重复加了同一条边，导致某节点入度被多减，提前变成负数，后续判断失效
- 图不连通，但你只从 0 号节点开始 BFS —— 不行，必须初始化时就把所有入度为 0 的节点都塞进队列
- 节点编号从 1 开始，但入度数组只开了
n大小却用indeg[i]访问，i=1 时越界未报错，但值是脏数据
调试时直接打印 result.size() 和 n 对比，比看中间过程更可靠。
C++ Code Review Master
下载
组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。
std::stack 替换 std::queue 会改变结果顺序，但仍是合法拓扑序
Kahn 算法本身不规定「选哪个入度为 0 的节点先处理」，所以用栈只是改变了贪心策略：从「先进先出」变成「后进先出」，结果仍是拓扑序，只是不同。
影响点很实际：
- 如果题目要求字典序最小的拓扑序（比如节点是字符或带权重），就不能用普通队列或栈，得换成
priority_queue（小根堆） - 用
stack后，同一轮多个可选节点中，编号大的会先被处理，容易让人误以为“顺序错了”——其实没错，只是不唯一 - 性能上没差别，
stack和queue都是 O(1) 均摊操作
邻接表用 vector<vector>></vector> 还是 vector<unordered_set>></unordered_set>
除非你需要频繁查「u→v 是否有边」，否则一律用 vector<vector>></vector>。理由很实在：
- 拓扑排序过程中，你只遍历出边，不查边是否存在；用
unordered_set白占内存、白耗哈希时间 - 如果输入含重边（比如连续两次
addEdge(1,2)），用vector会存两条，导致indeg[2]被多减一次 —— 所以读边时得自己去重，或用set辅助判重 - 极端情况：节点数 10⁵，边数 10⁵，
unordered_set每个节点额外开哈希桶，内存可能翻倍，且 cache 不友好
真正需要查边存在的场景极少，比如动态删边再拓扑——那已经不是标准 Kahn 能解决的问题了。
拓扑排序难的从来不是代码几行，而是建图前想清楚节点怎么编号、重边怎么处理、空图或单点怎么兜底。这些地方一松劲，跑样例全过，交上去 WA 在第 37 个测试点。
