无向图检测环是否必须转换为双向有向图进行处理？

把无向边拆为两条反向有向边存储是无向图处理的通用标准实现，好处是可以直接复用有向图的邻接表存储逻辑，不需要单独为无向图开发独立的底层结构，兼容性和开发效率都更高。

你现在遇到的单条无向边被误判为环的问题，本质是直接套用了有向图的环检测逻辑，没有适配无向图的特性：无向边双向可达的特性，会导致遍历的时候从父节点走到子节点后，子节点的邻接表会包含父节点，如果不做过滤就会把“走回头路”的逻辑判定为环。

无向图的环检测有两种常用的实现方式，改造难度都很低：

• 第一种是在原有DFS逻辑的基础上增加父节点过滤，只需要给递归函数新增一个父节点参数，遍历邻接节点时跳过父节点即可，修改后的代码如下：

// 无向图环检测，返回true说明无环，false说明有环
bool NoCyc(int node, vector<vector<int>>& pairs) {
    vector<vector<int>> graph(node);
    vector<int> visit(node, 0); // 0未访问，1访问中，2已访问完
    // 无向边双向存
    for (auto& edge : pairs) {
        int a = edge[0], b = edge[1];
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    for (int i = 0; i < node; ++i) {
        if (visit[i] == 0 && !dfs(graph, visit, i, -1)) {
            return false;
        }
    }
    return true;
}

bool dfs(vector<vector<int>>& graph, vector<int>& visit, int cur, int parent) {
    if (visit[cur] == 1) return false; // 遇到当前遍历路径里的节点，说明有环
    if (visit[cur] == 2) return true; // 已经处理完的节点直接跳过
    visit[cur] = 1; // 标记为当前路径访问中
    for (int next : graph[cur]) {
        if (next == parent) continue; // 跳过父节点，不走回头路
        if (!dfs(graph, visit, next, cur)) {
            return false;
        }
    }
    visit[cur] = 2; // 标记为处理完成
    return true;
}

• 第二种是更简便的并查集实现，无需递归，时间复杂度更低，对于大规模图的适配性更好。核心逻辑是遍历所有边前先初始化每个节点为独立集合，每次处理边时判断两个节点是否已经属于同一集合：如果是，说明两点已有其他连通路径，新增这条边就会形成环；如果不是，就把两个节点所在集合合并。代码实现如下：

class UnionFind {
private:
    vector<int> parent;
public:
    UnionFind(int n) {
        parent.resize(n);
        for (int i = 0; i < n; ++i) parent[i] = i;
    }
    int find(int x) {
        if (parent[x] != x) parent[x] = find(parent[x]); // 路径压缩
        return parent[x];
    }
    bool unite(int x, int y) {
        int fx = find(x), fy = find(y);
        if (fx == fy) return false; // 已经连通，加边就成环
        parent[fy] = fx;
        return true;
    }
};

bool NoCyc(int node, vector<vector<int>>& pairs) {
    UnionFind uf(node);
    for (auto& edge : pairs) {
        if (!uf.unite(edge[0], edge[1])) {
            return false;
        }
    }
    return true;
}

并查集方案仅适用于无向图的环检测，代码量更短，也不会出现DFS递归深度过高导致的栈溢出问题，更推荐优先使用。

内容的提问来源于stack exchange，提问作者user6703592