C++ 拓扑排序怎么从模板走向举一反三：入度统计、队列处理和环检测的面试训练
我在写拓扑排序模板时，经常会把图结构和入度数组弄混。面试里如果题目给的是依赖关系、课程关系或者任务先后关系，应该怎样用 C++ 组织数据，才能快速完成入度统计和邻接表构建？
用邻接表保存出边，用数组记录入度
可以把每条有向边看成“前置点指向后继点”。在 C++ 里通常用 vector<vector> 存邻接表，用 vector 存入度数组。遍历边集时，执行 graph[u].push_back(v) 表示 u 能到 v，同时让 indegree[v] 加一。这样做的好处是，后续处理时可以直接从当前节点找到所有后继节点，也能通过入度判断哪些点已经可以进入队列。若题目节点编号从 1 开始，数组开到 n + 1 会更方便；如果节点是字符串或稀疏编号，可以先做离散化再建图。
我能写出拓扑排序代码，但面试官常问为什么队列里只放入度为 0 的点。这个判断背后的含义是什么，怎么用通俗但严谨的方式说明它能保证顺序正确？
入度为 0 代表当前没有未完成的前置依赖
入度为 0 的节点，表示它已经没有任何必须先完成的前驱节点，因此它可以被安排到当前序列中。队列保存的正是这些“可立即处理”的节点。每次取出一个节点后，相当于把它从图中移除，于是它指向的后继节点入度会减一；当某个后继节点的入度减到 0，就说明它的所有前置条件都已经满足，也可以进入队列。这个过程保证了每个节点在被输出时，它的所有依赖都已经被处理过，所以得到的序列一定满足拓扑约束。
我知道有些题目不能直接做拓扑排序，因为图里可能存在环。面试时如果要求判断课程是否能全部完成，或者任务能否按依赖执行，应该怎样利用拓扑排序结果识别出环？
看能否处理完全部节点
利用 Kahn 算法时，可以统计实际出队并处理的节点数量。若最终处理的节点数等于总节点数，说明图中不存在有向环；若处理数量小于总节点数，说明还有一些节点始终无法变成入度为 0，这些节点一定处在环中，或被环间接阻塞。因为在有向无环图里，至少会存在一个入度为 0 的点，队列可以持续推进；而一旦存在环，环上的节点彼此依赖，入度不会被完全消除，队列会提前为空。这个判断方法是面试中最常用也最稳妥的环检测方式。
有些题目表面上看不像拓扑排序，比如课程安排、任务调度、构建依赖、模块加载顺序。遇到这类题时，我怎样快速识别它们和拓扑排序的关系，并把模板迁移过去？
先找依赖关系，再把问题转成有向图
这类题的核心通常都是“谁必须在谁前面完成”。只要能把条件抽象成有向边，就能转成拓扑排序问题。例如课程先修关系可以表示为先修课指向当前课，模块依赖可以表示为被依赖模块指向依赖它的模块，任务执行顺序也可以按前置条件建图。接着统计入度、用队列推进、输出顺序，就能得到一条合法执行链。如果题目要求判断是否可行，就用是否处理完全部节点来判断；如果要求最早完成时间，还可以在拓扑序上继续做动态规划，把前驱状态传递给后继节点。