检测有向图中的循环
为节点着色以找出回边
检测有向图中的循环 是 CoddyKit 上的免费 Competitive Programming Academy 课时。 这是第 2 节课，共 4 节。 你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。 这是 Competitive Programming Academy 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 Competitive Programming Academy 课程共包含 4 节课。
环为何重要
有向环意味着依赖关系形成了自我回路。发现环就意味着不存在拓扑序或有效的调度方案。
无向图有所不同
这里的环检测关注的是方向。沿错误的方向跟随边不算，因此无向图中的技巧并不适用。
三色标记法
为每个节点指定三种颜色之一：白色表示未访问，灰色表示正在处理，黑色表示已经完全处理。
WHITE, GRAY, BLACK = 0, 1, 2
color = [WHITE] * n灰色表示仍在栈中
一个灰色节点位于当前 DFS 路径上。您已经进入了它，但还没有完成对其所有后代的探索。
进入一个节点
当 DFS 到达一个节点时，请在探索之前将其标为灰色。这表示它属于当前活动路径。
def dfs(u):
color[u] = GRAY反向边信号
如果到达的邻居已经是灰色，就说明找到了指向当前路径的反向边。这就是一个环。
for v in adj[u]:
if color[v] == GRAY:
return True # cycle递归进入白色节点
白色邻居尚未被探索，因此请递归进入它。一旦更深层的调用报告发现了环，就立即向上返回 True。
elif color[v] == WHITE and dfs(v):
return True黑色表示安全
黑色邻居已经完成探索且不包含环，因此可以忽略它。再次访问只会浪费时间。
完成一个节点
处理完所有邻居后，将该节点标为黑色。它会离开活动路径，并被标记为已完成。
color[u] = BLACK
return False覆盖每个连通分量
图可能是非连通的，因此请从每个仍为白色的节点开始 DFS，以确保检查整个图。
if any(color[u]==WHITE and dfs(u) for u in range(n)):
print('cycle')注意递归限制
很深的图可能导致 Python 的递归栈溢出。请提高限制，或使用显式栈重写 DFS。
import sys
sys.setrecursionlimit(300000)快速检查
在 DFS 期间，您到达了一个当前为灰色的邻居。刚刚发现了什么？
回顾：环检测
将节点依次标记为白色、灰色和黑色。DFS 期间遇到灰色邻居，说明存在反向边，从而证明存在有向环。🔁
常见问题解答
「检测有向图中的循环」课时是免费的吗？
是的 — 「检测有向图中的循环」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 Competitive Programming Academy 课程的其余内容，请升级到 CoddyKit PRO。 Competitive Programming Academy 课程共包含 4 节课。
「检测有向图中的循环」这节课中我会学到什么？
为节点着色以找出回边 你通过在浏览器中直接运行的动手代码来练习 Competitive Programming Academy，全天候 AI 导师会在你学习这节课的过程中回答你的问题。
学习 Competitive Programming Academy 需要有经验吗？
无需任何先前经验。CoddyKit 上的 Competitive Programming Academy 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。 这是第 2 节课，共 4 节。
「检测有向图中的循环」课时需要多长时间？
大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。
我能在这节 Competitive Programming Academy 课中编写并运行代码吗？
能。每节 Competitive Programming Academy 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。
此课程中的所有课时
- 使用 Kahn 算法进行拓扑排序
- 检测有向图中的循环
- 强连通分量
- 桥与割点