拓扑排序成功当且仅当结果数组大小等于节点数n；需初始化入度数组为0，用bfs处理入度为0的节点，遍历邻接表更新入度，若最终topo.size()≠n则图含环。

用C++实现图的拓扑排序，需基于有向无环图（DAG）结构，通过统计每个节点入度、将入度为0的节点逐层加入队列并剥离其出边，最终输出线性序列；若存在环，则无法排满所有节点。

构建邻接表与入度数组

定义图的顶点数 【n 必须大于 0】，用 vector> 存储邻接表，用 vector 记录每个节点的入度。输入边时，对每条 u→v 边执行 adj[u].push_back(v) 并令 indeg[v]++。

这一步不能省略初始化：indeg 数组必须全部置 0，否则未出现的节点入度可能是随机值。

初始化 BFS 队列

遍历 0 到 n−1 的所有节点，把 indeg[i] == 0 的节点 i 入队。这是唯一合法的起点集合——只有没有依赖的节点才能排在最前面。

注意：节点编号默认从 0 开始；若题目给的是 1-indexed 输入，读入后要统一减 1 再存入邻接表和入度数组。

执行 Kahn 主循环

步骤一：取队首节点 u，将其加入结果数组 topo。

C++14

C++14 对 C++11 的修正与增强版本，适合旧系统维护和较老工具链兼容。

下载

步骤二：遍历 adj[u] 中每个邻居 v，执行 indeg[v]--；若此时 indeg[v] == 0，则将 v 入队。

步骤三：重复步骤一和步骤二，直到队列为空。

这一步中，每次只处理一个入度归零的节点，且仅当其所有前驱都被弹出后才轮到它——这正是拓扑序的本质约束。若图中存在环，某些节点的入度将永远无法减到 0，它们不会被加入 topo 数组。

判断是否为 DAG 并输出结果

方法一：比较 topo.size() 与 n。若相等，说明所有节点都被成功排序，输出 topo 中每个元素。

方法二：若 topo.size()

这一步不可跳过：不检查长度就输出 topo，可能漏掉环导致的无效结果。

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