并查集 (Disjoint Set Union)

并查集（DSU / Union-Find）用于处理集合的合并以及查询两个元素是否处于同一集合的问题。在同时采用路径压缩与按秩/按大小合并后，单次操作的均摊时间复杂度为反阿克曼函数 \(\mathcal{O}(\alpha(n))\)，几乎等于常数 \(\mathcal{O}(1)\)。

---

经典并查集模版

支持查询连通块大小与连通块数量，0-indexed 与 1-indexed 通用。

#include <vector>
#include <numeric>

struct DSU {
    int n;
    int components;        // 连通块数量
    std::vector<int> parent;
    std::vector<int> sz;    // 所在连通块大小

    DSU(int n) : n(n), components(n), parent(n), sz(n, 1) {
        std::iota(parent.begin(), parent.end(), 0);
    }

    // 路径压缩查找根节点
    int find(int i) {
        if (parent[i] == i) return i;
        return parent[i] = find(parent[i]);
    }

    // 按大小合并两个集合
    bool unite(int i, int j) {
        int root_i = find(i);
        int root_j = find(j);
        if (root_i == root_j) return false;

        if (sz[root_i] < sz[root_j]) {
            std::swap(root_i, root_j);
        }
        parent[root_j] = root_i;
        sz[root_i] += sz[root_j];
        components--;
        return true;
    }

    bool same(int i, int j) {
        return find(i) == find(j);
    }

    int size(int i) {
        return sz[find(i)];
    }
};

---

带权并查集 (Weighted DSU)

在维护集合归属关系的同时，维护节点与其祖先节点之间的某种相对偏移量（如距离差、模运算关系）。常用于差分约束或种类并查集（如食物链问题）。

struct WeightedDSU {
    int n;
    std::vector<int> parent;
    std::vector<long long> weight; // weight[x] 表示 x 与 parent[x] 的权值差 (x - parent[x])

    WeightedDSU(int n) : n(n), parent(n), weight(n, 0) {
        std::iota(parent.begin(), parent.end(), 0);
    }

    int find(int i) {
        if (parent[i] == i) return i;
        int orig_parent = parent[i];
        parent[i] = find(parent[i]);
        weight[i] += weight[orig_parent]; // 路径压缩时更新权值
        return parent[i];
    }

    // 合并并建立关系: val(j) - val(i) = w
    bool unite(int i, int j, long long w) {
        int root_i = find(i);
        int root_j = find(j);
        if (root_i == root_j) {
            // 验证是否矛盾
            return (weight[j] - weight[i] == w);
        }
        // parent[root_j] = root_i
        parent[root_j] = root_i;
        weight[root_j] = weight[i] - weight[j] + w;
        return true;
    }
};

---

复杂度分析

操作	时间复杂度	空间复杂度
初始化	\(\mathcal{O}(n)\)	\(\mathcal{O}(n)\)
find(x)	均摊 \(\mathcal{O}(\alpha(n))\)	\(\mathcal{O}(n)\)
unite(x, y)	均摊 \(\mathcal{O}(\alpha(n))\)	\(\mathcal{O}(n)\)
same(x, y)	均摊 \(\mathcal{O}(\alpha(n))\)	\(\mathcal{O}(n)\)

---

LeetCode 经典真题精选与题解提示

• LeetCode 200 - 岛屿数量 (Number of Islands) 中等

  提示

  二维网格连通块合并。

  • 将二维坐标 \((r, c)\) 映射为一维标号 \(r \times n + c\)。
  • 初始时每个陆地格自成独立集合，遍历每个陆地时向右、向下连通并调用 unite，最终连通块数量即为集合数。

• LeetCode 547 - 省份数量 (Number of Provinces) 中等

  提示

  并查集连通分量计数基石。

  • 初始时有 \(n\) 个城市独立集合。遍历邻接矩阵，若 \(isConnected[i][j] == 1\) 则合并两城市集合，每次成功合并连通块数 \(-1\)。

• LeetCode 684 - 冗余连接 (Redundant Connection) 中等

  提示

  无向图加边判环成树。

  • 树添加一条边必然构成唯一环。
  • 顺序遍历每条边 \((u, v)\)：若 same(u, v) 已成立，说明该边连接的两点已在同一连通块内，此边即为导致成环的冗余边！

• LeetCode 990 - 等式方程的可满足性 (Satisfiability of Equality Equations) 中等

  提示

  关系划分（先合并后校验）。

  • 第一阶段：遍历所有形如 a==b 的等式，调用 unite(a, b) 将具有等价关系的变量合并到同一集合；
  • 第二阶段：遍历所有形如 a!=b 的不等式，检查 same(a, b) 是否成立。若成立则与不等式自相矛盾，直接返回 false。

• LeetCode 765 - 情侣牵手 (Couples Holding Hands) 困难

  提示

  置换环分解与并查集连通分量。

  • 将编号 \(2i\) 与 \(2i+1\) 视为同一对情侣，共有 \(N\) 对情侣。将相邻的两个座位 \((2k, 2k+1)\) 视为一个沙发。
  • 对每个沙发上坐着的两个人所属的情侣编号进行 unite，构成若干置换环。每个大小为 \(k\) 的置换环需要 \(k - 1\) 次交换才能完全归位。总最少交换次数等于 \(N - \text{连通块数量}\)。

• LeetCode 827 - 最大人工岛 (Making A Large Island) 困难

  提示

  连通块带权大小合并。

  • 第一次遍历：并查集维护各原始岛屿连通块，并在根节点统计各岛屿面积大小 \(size\)；
  • 第二次遍历：枚举所有水格 0，通过四邻域查找相邻的所有不同岛屿根节点（使用哈希集合去重防重复累加），将各不同邻居面积相加再加 1，取全局最大值。