c++中用kahn算法实现拓扑排序需构建邻接表和入度数组，初始化队列加入所有入度为0的节点，bfs中每弹出一节点即更新邻接点入度并仅在减至0时入队，最终若结果序列长度等于节点数则成功，否则存在环。

要在C++中实现图的拓扑排序，且要求使用Kahn算法（即基于入度统计的BFS方法），必须先构建有向图、准确计算每个节点入度、将入度为0的节点入队，并在BFS过程中动态更新邻接节点入度；若最终输出序列长度不等于节点总数，说明图中存在环，排序失败。

构建邻接表与入度数组

用vector>存储邻接表，用vector记录每个节点的入度。节点编号从0开始，因此入度数组大小应为节点数n。

遍历所有有向边u→v，执行adj[u].push_back(v)和inDegree[v]++。这一步不能颠倒：先加边再增入度，否则inDegree[v]会漏统计。

注意：输入边时若节点编号从1开始，需统一减1转为0-indexed，否则inDegree数组访问越界。

初始化队列并加入所有入度为0的节点

使用queue，遍历0到n-1，对每个满足inDegree[i] == 0的i执行q.push(i)。

这一步必须在BFS主循环前完成，且不可遗漏任何入度为0的起点——哪怕只有一个，漏掉就会导致后续节点永远无法入队，结果序列不完整。

执行BFS核心流程

① 弹出队首节点u，将其加入拓扑序列result；

C++ 算法竞赛自动化测试数据生成与校验框架

根据原题生成新题面、验证器及完整测试数据，自动套用 testlib 模板，用于用户要求生成测试数据时。

下载

② 遍历adj[u]中每个邻接点v，执行inDegree[v]--；

③ 若inDegree[v]变为0，立即将v入队；

④ 重复直到队列为空。

关键点在于：只有当inDegree[v]减到0时才入队，不是减完就无条件入队。过早入队会导致同一节点多次加入，破坏BFS层级性和唯一性。

判断是否存在拓扑序

方法一：比较result.size()与n是否相等。相等则存在拓扑序，返回result；否则返回空vector，表示图含环。

方法二：额外维护一个count变量，在每次弹出节点时++，最后检查count == n。两种方式等价，但方法一更直观，无需新增变量。

【result必须用vector而非int[]，否则无法安全返回】

C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！