dfs递归栈判环最直接：用visited记录全局访问、on_stack标记当前路径，遇已入栈未回溯节点即存在环；kahn算法通过拓扑排序失败（输出节点数＜总节点数）判环，适合需线性序场景；vector有底层陷阱，建议改用vector。
用 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> 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
<h3>拓扑排序失败即存在环</h3>
<p>Kahn 算法做拓扑排序时，若最终输出的节点数少于图中总节点数，说明存在环。这方法天然适合需要同时判环 + 获取线性序的场景（比如任务调度）。</p>
<p>关键细节：</p><div class="aritcle_card flexRow artxards">
<div class="artcardd flexRow">
<a class="aritcle_card_img" rel="nofollow" href="/xiazai/skill5502" title="C++ Code Review Master"><img
src="https://img.php.cn/upload/skill/000/000/081/179051228971575.jpg" alt="C++ Code Review Master" onerror="this.onerror='';this.src='/static/lhimages/moren/morentu.png'" ></a>
<div class="aritcle_card_info flexColumn">
<a rel="nofollow" href="/xiazai/skill5502" title="C++ Code Review Master" class="overflowclass">C++ Code Review Master</a>
<p class="overflowclass">组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。</p>
</div>
<a rel="nofollow" href="/xiazai/skill5502" title="C++ Code Review Master" class="aritcle_card_btn flexRow flexcenter"><b></b><span>下载</span>
</a>
</div>
</div>
<ul>
<li>入度数组 <code>indeg</code> 初始化必须准确，空节点也要计入（哪怕没边）</li>
<li>队列初始只加入 <code>indeg[i] == 0</code> 的节点；每次弹出节点后，要遍历其所有邻接点 <code>v</code>，并执行 <code>--indeg[v]</code>，再检查是否为 0</li>
<li>如果图含自环（<code>u → u</code>），该边会让 <code>indeg[u]</code> 增加又减少，但初始入度不会为 0，仍会被正确识别为环</li>
</ul>
<p>代码骨架：</p>
<pre class="brush:php;toolbar:false;">vector<int> indeg(n, 0);
for (int u = 0; u q;
for (int i = 0; i
<h3>用 std::vector<bool> 存状态容易踩坑</bool>
</h3>
<p><code>std::vector<bool></bool></code> 是特化模板，底层按位存储，不支持取地址、迭代器行为异常，当你要传 <code>&on_stack[u]</code> 或用指针操作时会编译失败或运行时 UB。</p>
<p>稳妥做法：</p>
<ul>
<li>统一用 <code>vector<char></char></code> 或 <code>vector<int></int></code> 替代 <code>vector<bool></bool></code> 存 <code>visited</code> 和 <code>on_stack</code>
</li>
<li>如果坚持用 <code>bool</code>，务必避免取地址、用 <code>std::fill</code> 而非循环赋值、不拿 <code>operator[]</code> 返回值做左值</li>
<li>Clang/GCC 在 -O2 下对 <code>vector<bool></bool></code> 的优化可能掩盖问题，调试时尤其要小心</li>
</ul>
<h3>稀疏图和稠密图对算法选择影响不大</h3>
<p>DFS 和 Kahn 都是 O(V + E) 时间复杂度，空间也是 O(V + E)。实际选哪个，主要看需求，而不是图密度：</p>
<ul>
<li>只要判环，DFS 更轻量，代码短，栈空间可控（除非图极深导致爆栈）</li>
<li>需要拓扑序、或图带权重/需后续调度逻辑，Kahn 更自然</li>
<li>DFS 递归深度接近 10⁵ 时，建议改用显式栈模拟，避免系统栈溢出；Kahn 则无此风险</li>
</ul>
<p>真正容易被忽略的是：图中节点编号是否连续？是否有孤立点？是否含重边？这些都会影响 <code>indeg</code> 初始化和 DFS 起点枚举范围——别假设输入一定规整。</p></int>C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
