无向图存在环当且仅当dfs过程中遇到已访问且非父节点的邻接点；需为每个节点维护父节点参数以避免将父边误判为环，且须双向建图、遍历所有连通分量。
用DFS遍历判断无向图是否有环
无向图中存在环的充要条件是：DFS过程中遇到「已访问但非父节点」的邻接点。关键不是看有没有回边，而是看当前节点的邻居是否已被访问过，且那个邻居不是自己上一层的父节点。
实现时必须传入父节点信息，否则会把刚走过的边误判为环。比如从 A 到 B，再从 B 看到 A，若不记录父节点，就会错误触发环判定。
- 用
vector<vector>></vector>存邻接表，visited数组标记状态（未访问/正在访问/已结束） - DFS函数签名建议为：
bool dfs(int u, int parent) - 对每个未访问节点调用
dfs(u, -1)，避免遗漏多个连通分量 - 遇到邻接点
v满足visited[v] && v != parent，立刻返回true
并查集（Union-Find）检测无向图环
适用于边列表输入场景，尤其在构建图的过程中动态检测环——比如 Kruskal 算法里加边前先检查是否成环。
原理很简单：每条边 (u, v)，如果 find(u) == find(v)，说明 u 和 v 已连通，再连就成环；否则执行 union(u, v)。
C++ Code Review Master
下载
组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。
- 注意无向图每条边只处理一次，不要重复添加
(v, u) - 路径压缩 + 按秩合并可让单次操作接近
O(α(n)) - 初始化时每个节点自成集合：
parent[i] = i - 若图含重边，需先去重，否则同一对节点多次
union可能误报环
为什么BFS不适合直接判环
BFS也能做，但逻辑比DFS绕：需要记录每个节点的「层级」或「父来源」，并在访问邻接点时判断是否已访问且不是父节点——这本质上退化为带父指针的BFS，和DFS差异不大。
真正的问题在于：BFS天然不维护调用栈上下文，没法自然携带「父节点」参数；强行模拟会导致代码冗余、易错，比如忘记更新父映射或覆盖旧值。
- 若坚持用BFS，推荐用
queue<pair int>></pair>存(node, parent) - 不能只靠
visited[node]判断，必须对比parent字段 - 相比DFS，BFS多出队列管理、配对解包等开销，无实际优势
常见坑：邻接表建图时漏掉双向边
无向图的边是双向的，但新手常只加 adj[u].push_back(v)，漏掉 adj[v].push_back(u)，导致图不连通或部分节点不可达，从而漏判环。
- 读入一条边
u v后，必须执行两行：adj[u].push_back(v)和adj[v].push_back(u) - 若节点编号从1开始，确保
adj大小至少为n+1 - 使用
vector时，别用resize(n)后又用adj[u].push_back(...)，容易越界；应设为adj.resize(n + 1) - 测试用例包含孤立点（度为0）时，DFS主循环仍需遍历所有节点索引，不能只按边遍历
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
