用dfs判断有向图是否存在环的核心是追踪当前递归路径，通过三色法（白/灰/黑）或显式递归栈检测灰色节点或栈中重复节点，需遍历所有未访问起点，时间复杂度o(v+e)。
用深度优先搜索（DFS）判断有向图是否存在环路，核心是追踪“当前递归路径”——只要在遍历过程中发现某节点被再次访问，且它还处于当前调用栈中，就说明存在环。
状态标记三色法
给每个节点标记三种状态：
- 未访问（白色）：还没开始处理这个节点
- 访问中（灰色）：已进入DFS递归，但尚未回溯退出（即还在当前路径上）
- 已访问（黑色）：DFS已完整遍历完该节点及其所有后代，可安全忽略
当从节点 u 遍历到邻接点 v 时，若 v 是灰色，说明 v 在当前路径中，u→v 构成一条后向边，必然存在环（比如 u→…→v→…→u）。
递归栈显式跟踪
不依赖颜色标记，也可用一个布尔数组或哈希集合记录当前递归栈中的节点：
- 进入DFS函数前，把当前节点加入栈
- 对每个邻接节点递归调用前，先检查它是否已在栈中 → 是则直接返回“有环”
- 递归返回后，从栈中移除当前节点
这种方法逻辑更直观，适合调试和教学，时间开销与三色法一致，都是 O(V + E)。
需遍历所有起点
有向图可能不连通，单次DFS可能覆盖不到全部节点：
- 要对每个未访问过的节点都启动一次DFS
- 只要任意一次DFS中检测到灰色邻接点，即可提前终止并判定有环
- 若所有节点都走完且没触发环条件，说明图无环
注意：不能只从入度为0的节点开始（有些环可能孤立，如自环 3→3 或纯环 1→2→1），必须全覆盖。
实际编码关键细节
写代码时容易出错的地方：
- 状态更新顺序：访问节点 → 标灰 → 遍历邻居 → 回溯前标黑，不能颠倒
- 邻接表遍历中，不要跳过已标黑的节点（那是正常终止），只对灰节点敏感
- 自环（v→v）属于最短环，DFS中访问自己时立刻能捕获（v 的邻接列表含 v，且 v 此时是灰）
- 语言层面注意递归栈深度，大规模图建议用迭代DFS+显式栈避免爆栈
不复杂但容易忽略
