在数据结构中，并查集（Union-Find，又称 Disjoint Set Union） 是一种用于高效管理和处理元素分组（即“集合”）的结构，主要支持两种核心操作：合并两个集合和查询元素所属集合。它在解决“动态连通性”问题（如判断元素间是否存在连接关系、合并连接组件等）中表现优异，时间复杂度接近常数级。

一、并查集的核心需求

并查集要解决的问题可以抽象为：

  • 有 n 个元素，初始时每个元素自成一个独立集合（{a}, {b}, {c}, ...）。
  • 需要支持两种操作：
    1. Union（合并）：将两个元素所在的集合合并为一个集合。
    2. Find（查询）：确定一个元素属于哪个集合（通常用“根节点”标识集合）。
  • 最终目标：高效判断两个元素是否属于同一集合（通过比较根节点是否相同）。

二、并查集的基本实现思路

并查集的底层通常用数组（或哈希表）存储元素与父节点的关系，数组索引代表元素，数组值代表该元素的“父节点”。

1. 初始状态

每个元素的父节点是自身（parent[i] = i），表示每个元素单独构成一个集合，根节点就是自己。

2. Find 操作（查询根节点）

  • 目的：找到元素 x 所在集合的根节点（根节点的父节点是自身）。

  • 过程：递归或循环查找 x 的父节点，直到找到 parent[x] = x 的节点。

    例：若 parent[2] = 1，parent[1] = 0，parent[0] = 0，则 Find(2) 的结果为 0（根节点）。

3. Union 操作（合并集合）

  • 目的：将元素 x 和 y 所在的集合合并。
  • 过程：
    1. 先找到 x 的根节点 rootX 和 y 的根节点 rootY。
    2. 若 rootX ≠ rootY，则将其中一个根节点的父节点设为另一个根节点（如 parent[rootY] = rootX），使两个集合合并。

三、并查集的优化

原始实现中，Find 和 Union 操作的时间复杂度可能退化为 O(n)（如集合形成链式结构）。通过以下两种优化，可将时间复杂度降至几乎 O(1)（严格来说是 O(α(n))，α 为阿克曼函数的反函数，增长极慢，可视为常数）。

1. 路径压缩

问题：Find 操作在查找根节点时，可能需要遍历一条长长的链（如 x → p → q → ... → root）。
优化：在 Find 操作中，将路径上所有节点的父节点直接指向根节点，缩短后续查询的路径。

例：原本 2 → 1 → 0（根），执行 Find(2) 后，直接让 2 的父节点变为 0，下次查询 2 可直接找到根。

实现（递归版）：

// 假设 parent 是全局或类内的 vector<int> 容器，存储父节点信息
int find(int x) {
    if (parent[x] != x) {
        // 路径压缩：将 x 的父节点直接指向根节点
        parent[x] = find(parent[x]);
    }
    return parent[x];
}

2. 按秩合并

问题：Union 操作中，若随意将一个集合合并到另一个集合，可能导致树的高度增加，影响后续 Find 效率。
优化：合并时，将“秩”（可表示树的高度或节点数量）较小的集合合并到秩较大的集合的根节点下，避免树过高。

  • 秩的定义：

    • 可以是树的高度（rank[i] 表示以 i 为根的树的高度）。
    • 也可以是集合的大小（size[i] 表示以 i 为根的集合的元素数量）。

    实现（按大小合并）： 

    // 假设parent和size是类内的vector<int>成员，find是类内的成员函数
    void unionSets(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX == rootY) {
            return;  // 已在同一集合，无需合并
        }
        // 将小集合合并到大集合的根下
        if (size[rootX] < size[rootY]) {
            parent[rootX] = rootY;
            size[rootY] += size[rootX];
        } else {
            parent[rootY] = rootX;
            size[rootX] += size[rootY];
        }
    }

四、并查集的完整实现

结合路径压缩和按秩合并，完整代码如下：

#include <vector>
using namespace std;

class UnionFind {
private:
    vector<int> parent;  // 存储每个元素的父节点
    vector<int> size;    // 存储每个集合的大小（用于按大小合并）

public:
    // 构造函数：初始化n个元素，每个元素自成一个集合
    UnionFind(int n) {
        parent.resize(n);
        size.resize(n, 1);  // 初始时每个集合大小为1
        for (int i = 0; i < n; ++i) {
            parent[i] = i;  // 父节点初始化为自身
        }
    }

    // 查找元素x所在集合的根节点（带路径压缩）
    int find(int x) {
        // 递归版路径压缩：将x的父节点直接指向根节点
        if (parent[x] != x) {
            parent[x] = find(parent[x]);  // 压缩路径
        }
        return parent[x];
    }

    // 合并元素x和y所在的集合（按大小合并）
    bool unionSets(int x, int y) {
        int rootX = find(x);  // 找到x的根
        int rootY = find(y);  // 找到y的根

        if (rootX == rootY) {
            return false;  // 已在同一集合，无需合并
        }

        // 将较小的集合合并到较大的集合中，减少树的高度
        if (size[rootX] < size[rootY]) {
            swap(rootX, rootY);  // 保证rootX是较大集合的根
        }
        parent[rootY] = rootX;    // 小集合的根指向大集合的根
        size[rootX] += size[rootY];  // 更新大集合的大小
        return true;
    }

    // 判断元素x和y是否属于同一集合
    bool isConnected(int x, int y) {
        return find(x) == find(y);
    }
};

五、并查集的应用场景

并查集因高效的合并与查询能力，广泛应用于以下场景：

  1. 连通分量问题
    • 例如：判断无向图中两个节点是否连通、计算图中连通分量的数量。
  2. Kruskal 最小生成树算法
    • 用于检测添加一条边是否会形成环（若两节点已在同一集合，则添加边会成环）。
  3. 元素分组与合并
    • 例如：朋友圈问题（“A 和 B 是朋友，B 和 C 是朋友，则 A、B、C 属于同一朋友圈”）。
  4. 离线处理动态连通性
    • 例如：处理一系列合并和查询操作，判断任意时刻两个元素是否连通。