是否存在仅当无向图无环时插入边的算法？求C++示例代码

要实现「仅当插入边后无向图不形成环时才执行插入」的逻辑，核心思路是检查待插入边的两个节点是否属于同一个连通分量：

• 若两个节点不在同一连通分量，插入边不会形成环，执行插入并合并两个连通分量
• 若两个节点已在同一连通分量，插入边会直接形成环，拒绝插入

最适合实现这个逻辑的数据结构是并查集（Disjoint Set Union, DSU），它能高效完成「查找节点根节点」和「合并连通分量」操作，时间复杂度近乎O(1)。

算法步骤 #

1. 初始化并查集，每个节点初始时属于自己的连通分量
2. 对待插入的边(u, v)：
   • 查找u和v的根节点
   • 根节点不同：合并两个连通分量，同时在图中添加这条边
   • 根节点相同：不执行插入操作（避免形成环）

C++ 示例代码 #

#include <iostream>
#include <vector>
#include <unordered_set>
using namespace std;

// 并查集实现
class DSU {
private:
    vector<int> parent;
public:
    DSU(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 rootX = find(x);
        int rootY = find(y);
        if (rootX == rootY) {
            return false;
        }
        parent[rootY] = rootX;
        return true;
    }
};

// 无向图类，支持无环边插入
class UndirectedAcyclicGraph {
private:
    DSU dsu;
    vector<unordered_set<int>> adj; // 邻接表存储图

public:
    UndirectedAcyclicGraph(int nodeCount) : dsu(nodeCount) {
        adj.resize(nodeCount);
    }

    // 尝试插入边u-v，返回是否插入成功（无环则成功）
    bool insertEdge(int u, int v) {
        if (dsu.unite(u, v)) {
            adj[u].insert(v);
            adj[v].insert(u);
            cout << "成功插入边 " << u << "-" << v << endl;
            return true;
        } else {
            cout << "插入边 " << u << "-" << v << " 失败：会形成环" << endl;
            return false;
        }
    }

    // 打印当前图的邻接关系（避免重复打印无向边）
    void printGraph() {
        cout << "当前图结构：" << endl;
        for (int i = 0; i < adj.size(); ++i) {
            cout << i;
            for (int neighbor : adj[i]) {
                if (neighbor > i) {
                    cout << " - " << neighbor;
                }
            }
            cout << endl;
        }
    }
};

int main() {
    // 初始化6个节点的图（节点编号0-5）
    UndirectedAcyclicGraph graph(6);

    // 构建初始图：0-1、0-2、2-3、4-5
    graph.insertEdge(0, 1);
    graph.insertEdge(0, 2);
    graph.insertEdge(2, 3);
    graph.insertEdge(4, 5);
    cout << "\n初始图：" << endl;
    graph.printGraph();

    // 有效插入：2-4
    cout << "\n尝试插入边2-4：" << endl;
    graph.insertEdge(2, 4);
    graph.printGraph();

    // 无效插入：1-3
    cout << "\n尝试插入边1-3：" << endl;
    graph.insertEdge(1, 3);
    graph.printGraph();

    return 0;
}

代码说明 #

• 并查集的find方法使用路径压缩，unite方法直接合并根节点，保证操作效率
• UndirectedAcyclicGraph类封装了图的存储和插入逻辑，插入前通过并查集判断是否会形成环
• 打印图时只输出单向边（neighbor > i），避免重复展示无向边

运行代码后，会输出初始图、有效插入后的图，以及无效插入的提示，完全匹配你给出的示例场景。

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