DFS递归栈判环最直接：用visited记录全局访问、on_stack标记当前路径，遇已入栈未回溯节点即存在环；Kahn算法通过拓扑排序失败（输出节点数＜总节点数）判环，适合需线性序场景；vector<bool>有底层陷阱，建议改用vector<char>。
用 DFS 递归栈判断环路最直接
有向图判环，DFS 是最常用也最容易落地的方法。核心思路是：在 DFS 过程中维护一个 on_stack 数组（或 recursion_stack），标记当前递归路径上正在访问的节点。一旦遇到一个已入栈但尚未回溯的节点，就说明存在环。
注意点：
-
visited和on_stack必须分开维护——visited记录全局访问过与否，on_stack只管当前 DFS 分支 - 必须在进入递归前设
on_stack[u] = true，回溯时立刻设on_stack[u] = false，顺序不能错 - 对每个未访问节点都要启动一次 DFS，不能只从 0 开始——有向图可能含多个不连通子图
示例片段（邻接表 graph，节点编号 0~n-1）：
bool has_cycle = false;
vector<bool> visited(n, false), on_stack(n, false);
function<void(int)> dfs = [&](int u) {
if (has_cycle) return;
visited[u] = true;
on_stack[u] = true;
for (int v : graph[u]) {
if (!visited[v]) {
dfs(v);
} else if (on_stack[v]) {
has_cycle = true;
return;
}
}
on_stack[u] = false;
};
for (int i = 0; i < n; ++i) {
if (!visited[i]) dfs(i);
}
拓扑排序失败即存在环
Kahn 算法做拓扑排序时，若最终输出的节点数少于图中总节点数，说明存在环。这方法天然适合需要同时判环 + 获取线性序的场景（比如任务调度）。
立即学习“C++免费学习笔记（深入）”；
关键细节：
C++ Code Review Master
下载
组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。
- 入度数组
indeg初始化必须准确，空节点也要计入（哪怕没边） - 队列初始只加入
indeg[i] == 0的节点；每次弹出节点后，要遍历其所有邻接点v，并执行--indeg[v]，再检查是否为 0 - 如果图含自环（
u → u），该边会让indeg[u]增加又减少，但初始入度不会为 0，仍会被正确识别为环
代码骨架：
vector<int> indeg(n, 0);
for (int u = 0; u < n; ++u)
for (int v : graph[u])
++indeg[v];
queue<int> q;
for (int i = 0; i < n; ++i)
if (indeg[i] == 0) q.push(i);
int cnt = 0;
while (!q.empty()) {
int u = q.front(); q.pop(); ++cnt;
for (int v : graph[u]) {
if (--indeg[v] == 0) q.push(v);
}
}
bool has_cycle = (cnt != n);
用 std::vector 存状态容易踩坑
std::vector<bool> 是特化模板，底层按位存储，不支持取地址、迭代器行为异常，当你要传 &on_stack[u] 或用指针操作时会编译失败或运行时 UB。
稳妥做法：
- 统一用
vector<char>或vector<int>替代vector<bool>存visited和on_stack - 如果坚持用
bool，务必避免取地址、用std::fill而非循环赋值、不拿operator[]返回值做左值 - Clang/GCC 在 -O2 下对
vector<bool>的优化可能掩盖问题，调试时尤其要小心
稀疏图和稠密图对算法选择影响不大
DFS 和 Kahn 都是 O(V + E) 时间复杂度，空间也是 O(V + E)。实际选哪个，主要看需求，而不是图密度：
- 只要判环，DFS 更轻量，代码短，栈空间可控（除非图极深导致爆栈）
- 需要拓扑序、或图带权重/需后续调度逻辑，Kahn 更自然
- DFS 递归深度接近 10⁵ 时，建议改用显式栈模拟，避免系统栈溢出；Kahn 则无此风险
真正容易被忽略的是：图中节点编号是否连续？是否有孤立点？是否含重边？这些都会影响 indeg 初始化和 DFS 起点枚举范围——别假设输入一定规整。
