并查集（DSU）

并查集概览

并查集（Disjoint Set Union，DSU）支持两种操作：Union（合并两个集合）和 Find（查询某元素属于哪个集合）。配合路径压缩与按秩合并，两种操作均摊近 O(1)（精确为反阿克曼函数 α(n)）。

操作复杂度

DSU vs BFS/DFS

基础实现

两个优化缺一不可：

两大优化

• 路径压缩：find() 时将沿途所有节点直接挂到根节点，使后续查询更快
• 按秩合并：union() 时将较矮的树挂到较高的树根下，控制树高不超过 O(log n)

// DSU with path compression + union by rank
struct DSU {
    vector<int> parent, rank;
    int components;

    DSU(int n) : parent(n), rank(n, 0), components(n) {
        iota(parent.begin(), parent.end(), 0); // parent[i] = i
    }

    int find(int x) {
        if (parent[x] != x)
            parent[x] = find(parent[x]); // path compression
        return parent[x];
    }

    bool unite(int x, int y) {
        int rx = find(x), ry = find(y);
        if (rx == ry) return false; // already connected
        if (rank[rx] < rank[ry]) swap(rx, ry);
        parent[ry] = rx;             // attach shorter tree under taller
        if (rank[rx] == rank[ry]) rank[rx]++;
        components--;
        return true;
    }

    bool connected(int x, int y) { return find(x) == find(y); }
};

按大小 vs 按秩：按秩（rank）合并与按大小（size）合并均可。按大小更直观（rank[] 换成 size[]，初始值为 1），效果相同。

加权并查集

加权 DSU 在 parent[] 之外维护 weight[] 表示节点到根的相对权重（如距离、比值）。find() 时同步压缩路径并累加权重，union() 时根据已知关系设置权重差。

典型题目

• 399. 除法求值（边权为比值，加权 DSU 存对数或比值）
• 1061. 字典序最小等价字符串（等价类合并）
• 547. 省份数量（基础连通分量计数）

注意：加权 DSU 的权重语义取决于问题定义。比值类问题常用乘法而非加法合并，需仔细推导路径压缩时的权重更新公式。

常见应用模式

模式速查

// Detect the first redundant edge in an undirected graph
int findRedundant(vector<pair<int,int>>& edges, int n) {
    DSU dsu(n + 1);
    for (auto& [u, v] : edges) {
        if (!dsu.unite(u, v)) return /* this edge is redundant */ u; // or track index
    }
    return -1;
}

// Kruskal's MST — sort edges by weight, add if not creating a cycle
int kruskal(int n, vector<tuple<int,int,int>>& edges) { // (weight, u, v)
    sort(edges.begin(), edges.end());
    DSU dsu(n);
    int totalCost = 0, edgesUsed = 0;
    for (auto& [w, u, v] : edges) {
        if (dsu.unite(u, v)) {
            totalCost += w;
            if (++edgesUsed == n - 1) break; // MST complete
        }
    }
    return totalCost;
}

典型题目

• 547. 省份数量
• 684. 冗余连接
• 685. 冗余连接 II（有向图）
• 721. 账户合并
• 399. 除法求值（加权）