dfs拓扑排序通过三色标记（unvisited/visiting/visited）检测环：遇visiting邻接点即存在环；kahn算法则通过最终拓扑序列长度是否等于节点总数来判环，更直观可靠。
用 DFS 记录访问状态判断环
拓扑排序本身不直接返回“是否有环”，但 DFS 实现的拓扑排序过程天然能检测环——关键在节点的访问状态标记。每个节点需区分三种状态：unvisited（未访问）、visiting（当前 DFS 路径中正访问）、visited（已彻底处理完）。一旦在 visiting 状态下再次遇到同一节点，就说明存在回边，即有环。
常见错误是只用 bool visited[] 二值标记，这会漏判：比如从 A→B→C→A，当回溯到 B 再访问 A 时，A 已被标为 true，但无法区分它是“已完成”还是“在当前路径中”。必须用三色标记。
实操建议：
组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。
- 用
vector<int> state</int>，0=unvisited，1=visiting，2=visited - DFS 进入节点时设为
1，退出前设为2 - 递归中若遇到
state[v] == 1，立即返回false（有环） - 所有节点都成功完成 DFS 后才返回
true（无环）
用 Kahn 算法的入度数组反推环
Kahn 算法本质是不断剥离入度为 0 的节点。如果图中存在环，环内所有节点的入度永远无法减到 0（因为环中每个节点至少有一条来自环内前驱的边），最终队列会变空，但仍有未输出的节点。
这是最直观、不易出错的环检测方式，尤其适合不想写递归或担心栈溢出的场景。
实操建议：
- 初始化
vector<int> indegree(n, 0)</int>，遍历所有边统计入度 - 把所有
indegree[i] == 0的节点入队 - 每弹出一个节点，对其邻接点
v执行indegree[v]--；若减为 0 则入队 - 算法结束后检查拓扑序列长度是否等于节点总数：
if (result.size() != n) → 有环
为什么不能只靠 std::sort 或自定义比较器模拟拓扑序
C++ 标准库没有内置拓扑排序函数，有人试图用 std::sort 配合自定义 comp 比较两个节点是否“可达”，这是危险的。拓扑序要求偏序关系可传递且无环，而任意两个节点间的可达性判断本身就需要 O(V+E) 时间，且 std::sort 假设比较函数满足严格弱序——但图中不可达的节点对无法定义一致大小关系，极易触发 std::sort 断言失败或未定义行为。
典型错误现象：expression: invalid comparator 或程序崩溃。
真正可行的做法只有两种：DFS 三色标记 或 Kahn 入度剥离。其他“捷径”都会在稀疏图、多连通分量或含自环时失效。
实际项目中要注意的边界情况
真实图数据常带干扰项，容易让环检测逻辑失效。
需要提前处理或校验：
- 自环：
u → u直接构成环，Kahn 中表现为indegree[u]初始 ≥1 且永远不会减到 0；DFS 中表现为立刻遇到state[u] == 1 - 孤立节点（无边）：不影响环判断，但 Kahn 中要确保它们初始
indegree == 0并被加入队列 - 多个连通分量：必须遍历所有节点启动 DFS 或确保 Kahn 初始化包含全部节点，否则遗漏分量会导致误判“无环”
- 节点编号不连续（如用 string 或 id 映射）：别硬套
vector下标，改用unordered_map<node int></node>存状态或入度
环检测不是黑盒调用，状态管理和图结构理解缺一不可。尤其当图由外部输入生成时，先做合法性检查比强行跑拓扑更省调试时间。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
