DFS判环最直接：用三态数组（0/1/2）标记节点，遇状态1的邻接点即成环；拓扑排序失败（入度不归零）或并查集在无向图中find(u)==find(v)也表明有环。
DFS遍历中用状态数组判环最直接
对有向图，DFS过程中维护三种节点状态：未访问（0）、正在访问（1）、已访问完毕（2）。一旦在递归中遇到状态为1的邻接点，说明当前路径成环。这是最常用且逻辑清晰的做法。
关键点：
-
state[v] == 1是环存在的充要条件，不是state[v] == 0或state[v] == 2 - 必须在进入递归前设
state[u] = 1，回溯时再置为2；只设一次1不清零会漏判 - 无向图需额外记录父节点，避免把
u→v→u误判为环；有向图不用
bool dfs(int u, vector<int>& state, const vector<vector<int>>& g) {
state[u] = 1;
for (int v : g[u]) {
if (state[v] == 1) return true; // 发现后向边
if (state[v] == 0 && dfs(v, state, g)) return true;
}
state[u] = 2;
return false;
}
拓扑排序失败意味着有环（适合有向图）
Kahn算法执行完若还有入度 > 0 的节点没被加入拓扑序，说明图含环。它天然适用于需要同时检测环+获取线性序的场景，比如任务调度校验。
注意：
立即学习“C++免费学习笔记（深入）”；
- 仅适用于有向图；无向图用此法会把所有边当双向边处理，必然失败
- 需要预计算每个节点的
indeg[v]，队列初始只推入indeg[v] == 0的点 - 每次弹出节点后，对其所有邻接点
v执行indeg[v]--，而非清零
如果最终加入拓扑序的节点数 < n，就确定存在环。
并查集只能判无向图的环
对无向图，边 (u, v) 加入前若 find(u) == find(v)，说明 u 和 v 已连通，再加这条边必成环。这是并查集最典型的应用之一。
但要注意：
- 完全不适用于有向图——方向性丢失，
union(u,v)无法表达u→v的语义 - 初始化时每个点自成集合：
parent[i] = i，别漏写 - 路径压缩必须做，否则多次查询后
find可能退化成 O(n)，影响整体效率
强连通分量（SCC）分解是重武器
用 Tarjan 或 Kosaraju 算法求出所有 SCC 后，只要存在大小 > 1 的 SCC，或某个 SCC 内部有自环（即存在 u→u 边），就说明原图有环。这方法开销大，但能定位环的具体位置和规模。
适用情形：
- 需要区分“纯环”和“带环子图”，比如编译器做循环依赖分析
- 图非常稀疏但必须精确判断环结构，DFS 状态法可能因递归深度爆栈
- 后续还要基于 SCC 做缩点建 DAG，顺带完成判环
别为了单纯判环去写 Tarjan——代码量、调试成本和运行开销都远超前三种方法。
