拓扑排序前必须检查图是否有环，bfs结束后若存在入度大于0的节点则说明有环；需显式传入节点总数n以处理孤立点；用queue得任意合法序，用priority_queue可得字典序最小解。
拓扑排序前必须检查图是否有环
入度统计法本身不自动检测环，如果图含环，BFS结束后仍有节点入度非零，但队列已空——这是唯一可靠信号。别依赖“排序结果长度是否等于节点数”这种表面判断，因为图可能不连通，而你只从部分节点启动了遍历。
实操建议：
- 初始化时对每个节点记录入度，哪怕它没出现在任何边的终点（此时入度为 0）
-
BFS结束后遍历所有节点，检查是否存在indegree[v] > 0的节点v；有则说明存在环，拓扑序不存在 - 若图用邻接表
vector<vector>> graph</vector>存储，注意节点编号通常从 0 或 1 开始，入度数组大小必须匹配最大节点 ID + 1
用 queue 实现 BFS 时，入队时机决定顺序稳定性
queue 是 FIFO，但拓扑序不唯一——只要满足“所有前驱都在后继之前”，多个合法序列都对。如果你需要字典序最小的拓扑序（比如题目要求），就不能用 queue，得换 priority_queue（小根堆）。
常见错误现象：用 queue 得到的顺序和样例输出不一致，误以为算法错了。其实只是样例用了不同入队策略。
实操建议：
- 标准实现用
queue<int></int>即可，每次取任意一个入度为 0 的节点处理 - 若需字典序最小解，改用
priority_queue<int vector>, greater<int>></int></int>，并确保所有入度为 0 的节点都及时入堆（不能等上一个出堆后再扫描） - 不要在 BFS 过程中动态修改图结构（如删边），统一用入度减法模拟“删除节点”
邻接表构建与入度更新必须同步且无重复边
重复添加同一条边（如 u → v 加了两次）会导致 indegree[v] 被多减一次，最终可能把不该入队的节点提前放进去，或让真实入度为 0 的节点残留非零值。
使用场景：读取文件或控制台输入边时，容易因格式问题（空行、多余空格）触发重复解析。
实操建议：
- 建图前用
set<pair int>></pair>去重，或在加边前判断graph[u]是否已含v（适合小规模） - 每处理一条边
u → v，只做两件事：graph[u].push_back(v)和indegree[v]++ - 注意方向：是
u → v，就影响v的入度，不是u的 - 若输入含自环（
u → u），直接拒绝——自环必然导致环，可提前报错
完整可运行代码的关键边界处理
下面是最简可用版本，已包含环检测、安全初始化和标准 BFS 流程：
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
vector<int> topoSort(const vector<vector>>& graph, int n) {
vector<int> indegree(n, 0);
for (int u = 0; u q;
for (int i = 0; i res;
while (!q.empty()) {
int u = q.front(); q.pop();
res.push_back(u);
for (int v : graph[u]) {
indegree[v]--;
if (indegree[v] == 0) q.push(v);
}
}
if ((int)res.size() != n) return {}; // 有环
return res;
}
</int></vector></int></queue></vector></iostream>
容易被忽略的地方：参数 n 必须显式传入——C++ 邻接表无法从 graph.size() 推出总节点数，因为孤立点不会出现在任何 graph[u] 中，也不会作为边的终点出现，但仍是图的一部分。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
