拓扑排序必须先检测环，仅适用于有向无环图（DAG）；DFS法用三色标记判环并逆序记录节点，BFS法（Kahn算法）通过入度为0入队及最终结果长度判环，更直观易实现。
拓扑排序需要先判断图是否有环
拓扑排序只对有向无环图（DAG）有效，如果图含环，topological_sort 无法给出合法序列。实际写代码时，不能跳过环检测——否则可能得到错误结果或无限循环。
常见做法是：在 DFS 或 BFS 过程中同步记录节点状态。比如用三个值标记节点：unvisited、visiting（当前递归栈中）、visited。一旦遇到 visiting 状态的邻接点，就说明成环。
- DFS 实现时，回溯前把节点设为
visited；进入递归前设为visiting - BFS 实现（Kahn 算法）中，若最终加入结果的节点数
!=总节点数，说明有环 - 注意：输入图可能不连通，需遍历所有节点启动 DFS 或检查所有入度为 0 的起点
Kahn 算法更易实现且天然支持环检测
相比 DFS 版本，Kahn 算法用队列和入度数组，逻辑更直白，也更容易调试。它模拟“不断剥离没有前置依赖的节点”的过程。
关键步骤：
立即学习“C++免费学习笔记（深入）”；
- 统计每个节点的入度，把所有
in_degree[i] == 0的节点入队 - 每次取出队首
u，加入结果 vector，并遍历其所有邻接点v，执行in_degree[v]--；若减为 0，立即入队 - 算法结束时，检查
result.size() == N，否则存在环
示例片段（假设节点编号 0 ~ N-1，graph 是邻接表）：
C++ Code Review Master
下载
组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。
vector<int> topological_sort(const vector<vector<int>>& graph) {
int n = graph.size();
vector<int> in_degree(n, 0);
for (int u = 0; u < n; ++u)
for (int v : graph[u])
in_degree[v]++;
queue<int> q;
for (int i = 0; i < n; ++i)
if (in_degree[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]) {
if (--in_degree[v] == 0) q.push(v);
}
}
return res.size() == n ? res : vector<int>{}; // 返回空表示有环
}
DFS 版本要注意递归顺序和结果翻转
DFS 拓扑排序本质是按“离开时间逆序”排列节点，所以必须在 dfs(u) 所有邻接点处理完后，才把 u 压入结果。这意味着最终结果要反转，或者用 deque 前插。
容易出错的地方：
- 误在进入
dfs(u)时就 push，导致顺序错乱 - 忘记对每个未访问节点调用 DFS（图不连通时漏节点）
- 状态数组没初始化或复用错误，多组测试时出问题
简写示意（仅核心逻辑）：
void dfs(int u, const vector<vector<int>>& graph, vector<int>& state, vector<int>& res) {
state[u] = 1; // visiting
for (int v : graph[u]) {
if (state[v] == 0) dfs(v, graph, state, res);
else if (state[v] == 1) throw runtime_error("cycle detected");
}
state[u] = 2; // visited
res.push_back(u); // 离开时记录
}
// 调用后需 reverse(res.begin(), res.end())
实际使用时优先考虑标准容器与索引稳定性
如果你的节点不是简单整数（比如是字符串、指针或自定义 ID），别硬套 0~N-1 下标。建议先做映射：map<string, int> id_map，统一转成整数索引再建图；否则 vector<vector<int>> 无法直接使用。
另外注意：
-
vector<vector<int>>存稀疏图可能浪费内存，但访问快；超大图可改用vector<unordered_set<int>>去重边 - 多次调用拓扑排序时，避免重复构造图结构——把图和入度数组作为类成员缓存
- STL 没有内置拓扑排序函数，
<algorithm>里没有topological_sort，别白找
真正卡住的往往不是算法逻辑，而是节点标识混乱、环检测漏判、或对空图/单点图的边界没处理。
