拓扑排序成功执行的充要条件是图为有向无环图（DAG），入度统计+BFS（Kahn算法）最稳妥，因其天然支持环检测：最终结果长度小于节点总数即存在环，且避免了DFS中环检测遗漏或顺序错误的问题。
拓扑排序能成功执行，只有一种情况：图是有向无环图（DAG）。只要检测到环，topological_sort 就该返回空结果或报错，而不是强行输出一个“看似有序”的序列。
为什么入度统计 + BFS 是最稳妥的实现方式
DFS 实现拓扑排序容易漏掉环检测逻辑，或在回溯时顺序处理不当导致结果错误；而入度统计法天然契合 Kahn 算法本质——每次只选「当前没有前置依赖」的节点。它不依赖递归栈状态，环检测直接体现在最后是否还有剩余入度 > 0 的节点上。
关键点：
-
indegree[v]必须初始化为 0，再遍历所有边进行累加，不能靠 vector 默认值侥幸 - 队列（
queue<int></int>）只推入indegree[u] == 0的节点，且入队后立即把indegree[u]设为 -1 或用布尔数组标记已访问，避免重复入队 - 每弹出一个节点
u，要遍历其所有邻接点v，并对每个v执行indegree[v]--；若减后为 0，才入队 - 最终结果长度若小于图中节点总数，说明存在环 —— 这是唯一可靠的环判定依据
代码里最容易写错的三处边界
实际调试时，90% 的失败不是算法逻辑错，而是这些细节没对齐：
立即学习“C++免费学习笔记（深入）”；
- 图的节点编号是否从 0 开始？如果输入边是 1-indexed（如
1 2表示 1→2），但你用vector<vector>> graph(n)</vector>，就会越界。务必统一偏移：u--, v-- -
graph邻接表大小必须是n，不是n+1（除非你刻意留出 index 0 不用）；否则graph[u].push_back(v)可能写到未分配内存 - 当
n == 0或边集为空时，indegree数组仍需正确初始化，BFS 队列应把所有入度为 0 的节点（即全部节点）都推进去 —— 否则结果缺失
一个极简可运行的 C++ 版本（含环检测）
以下代码去掉注释后不到 30 行，可直接编译验证：
#include <vector>
#include <queue>
#include <iostream>
using namespace std;
vector<int> topological_sort(int n, const vector<vector<int>>& edges) {
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> 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);
}
}
return res.size() == n ? res : vector<int>{}; // 有环则返回空
}
调用示例：topological_sort(4, {{0,1},{0,2},{1,3},{2,3}}) 返回 {0,1,2,3}；topological_sort(3, {{0,1},{1,2},{2,0}}) 返回空 vector。
真正难的不是写出这个框架，而是面对一个真实项目里的混合图结构（比如带权重、节点带属性、边来自 JSON 配置）时，能否快速把原始数据映射成干净的 int 节点编号 + 边列表。那个映射过程，往往比排序本身更花时间，也更容易出错。
