拓扑排序的核心判断条件是图中是否存在环，即遍历结束后输出顶点数是否等于总顶点数；若不等则存在环，排序失败。
拓扑排序的核心判断条件是什么
拓扑排序只适用于有向无环图（DAG）。如果图中存在环，indegree[v] == 0 的节点在某轮遍历后彻底消失，队列/栈变空但仍有未访问节点——此时可直接判定环存在，排序失败。
实际编码中不能只看最终是否输出了全部顶点，必须检查输出顶点数是否等于图中顶点总数。否则就是隐含环，比如输入边 0→1、1→2、2→0 时，所有节点入度始终为 1，queue 从不入队，结果为空。
用 vector> 存邻接表 + indegree 数组怎么写
这是最常用、最易调试的实现方式。邻接表用 vector<vector>></vector>，每个 i 对应出边目标列表；入度单独开 vector<int> indegree(n, 0)</int>，初始化时遍历所有边做 indegree[to]++。
注意：顶点编号建议从 0 开始，避免下标越界；若输入是 1-based，读入后统一减 1 处理。
立即学习“C++免费学习笔记（深入）”；
- 使用
queue<int></int>实现 BFS 式拓扑序（推荐，顺序稳定） - 入队前务必检查
indegree[i] == 0，且入队后立即置为 -1 或用布尔数组标记已入队，防止重复入队 - 每次从队首取节点
u，遍历其所有邻接点v，执行indegree[v]--；若减到 0，立刻入队
vector<vector<int>> graph(n);
vector<int> indegree(n, 0);
for (auto& e : edges) {
int u = e[0], v = e[1];
graph[u].push_back(v);
indegree[v]++;
}
queue<int> q;
for (int i = 0; i < n; i++)
if (indegree[i] == 0) q.push(i);
vector<int> topo;
while (!q.empty()) {
int u = q.front(); q.pop();
topo.push_back(u);
for (int v : graph[u]) {
indegree[v]--;
if (indegree[v] == 0) q.push(v);
}
}
if (topo.size() != n) cout << "cycle detected" << endl;
为什么不能用 DFS 直接递归输出顺序
DFS 版拓扑排序不是简单地在访问时 push_back，而必须在「所有后继都访问完毕」之后才记录当前节点——即使用逆后序（post-order reverse）。否则顺序错乱，例如 A→B、A→C、B→C，DFS 若从 A 入口先走 B 再走 C，可能输出 A,B,C（错误），正确应是 A,B,C 或 A,C,B，但 C 不能在 B 前（因 B→C）。
常见错误是把 DFS 当成普通遍历，在 visit(u) 开头就加进结果，这实际得到的是某种访问序，不是拓扑序。
- 必须用状态数组区分
unvisited/visiting/visited，遇到visiting就说明成环 - 仅当递归返回前（即退出函数前）把
u加入结果，再 reverse 整个结果 - 多起点时需对每个未访问节点调用 DFS，不能只从 0 开始
AOV 网调度中如何处理多入度依赖与任务权重
AOV 网本身不带权，但实际调度常需扩展：比如任务耗时（权重）、资源约束、或多个前置任务必须全部完成才能开始（这正是入度统计的物理意义）。此时 indegree[u] 就是“还剩几个前置任务未完成”，只有归零才可调度。
若需计算最早开始时间（Earliest Start Time），可在拓扑序上 DP：est[v] = max(est[v], est[u] + duration[u])，前提是图按拓扑序遍历，且 u→v 是依赖边。
- 不要在建图时合并重复边，否则
indegree统计偏小，导致过早调度 - 若输入含重边（如两个文件都声明依赖同一头文件），需去重或用 set 存邻接表
- 并发调度时，同一轮中所有
indegree==0的节点可并行执行，这时 queue 可换为 vector 批量处理
入度统计看着简单，但边界全在细节里：初始化漏节点、重边不判、环检测不校验长度、多起点遗漏——这些都会让 AOV 调度在真实项目中静默失败。
