并查集（Disjoint Set Union, DSU）全面解析

一、基本概念

并查集是一种树型数据结构，用于高效处理不相交集合的合并（Union）与查询（Find）问题。其核心功能包括：

• 查找（Find）：确定元素所属集合的根节点。
• 合并（Union）：将两个集合合并为一个。
• 连通性判断：判断两个元素是否属于同一集合。

二、核心操作与优化

1. 查找（Find）

   • 目标：找到元素所在集合的根节点。
   • 优化：路径压缩
     在查找过程中，将路径上的所有节点直接指向根节点，降低后续查找的时间复杂度。

2. 合并（Union）

   • 目标：将两个集合合并为一个。
   • 优化：按秩合并
     将秩（树高或大小）较小的树合并到秩较大的树下，避免树的高度激增。

三、C++ 实现详解

1. 数据结构定义

• 父节点数组 parent[]：记录每个元素的直接父节点。
• 秩数组 rank[]：记录以当前节点为根的树的秩（通常为树高）。

#include <vector>

class UnionFind {
private:
    std::vector<int> parent;  // 父节点数组
    std::vector<int> rank;    // 秩数组（按树高合并）

public:
    // 构造函数：初始化每个元素的父节点为自身，秩为0
    UnionFind(int size) {
        parent.resize(size);
        rank.resize(size, 0);
        for (int i = 0; i < size; ++i) {
            parent[i] = i;
        }
    }

    // 查找操作（路径压缩）
    int find(int u) {
        if (parent[u] != u) {
            parent[u] = find(parent[u]);  // 递归压缩路径
        }
        return parent[u];
    }

    // 合并操作（按秩合并）
    bool unionSets(int u, int v) {
        int rootU = find(u);
        int rootV = find(v);
        
        if (rootU == rootV) return false;  // 已连通
        
        // 按秩合并：小秩树合并到大秩树
        if (rank[rootU] > rank[rootV]) {
            parent[rootV] = rootU;
        } else if (rank[rootU] < rank[rootV]) {
            parent[rootU] = rootV;
        } else {
            parent[rootV] = rootU;
            rank[rootU]++;  // 秩相同时，合并后秩+1
        }
        return true;
    }

    // 判断连通性
    bool connected(int u, int v) {
        return find(u) == find(v);
    }
};

2. 关键代码解析

• 路径压缩
  在 find 函数中，递归将路径上的节点父指针直接指向根节点，使树扁平化，后续操作时间复杂度接近 (O(1))。

• 按秩合并
  在 unionSets 中，通过比较两棵树的秩，决定合并方向。若秩相等，合并后新树的秩加1，避免树高无序增长。

四、时间复杂度分析

• 平均时间复杂度：(O(\alpha(n)))，其中 (\alpha(n)) 是阿克曼函数的反函数，其值通常小于5，接近常数。
• 最坏情况：(O(\log n))（未优化时为 (O(n))）。

五、使用示例

#include <iostream>

int main() {
    UnionFind uf(5);  // 初始化5个独立集合 {0}, {1}, {2}, {3}, {4}

    uf.unionSets(0, 1);  // 合并为 {0,1}, {2}, {3}, {4}
    uf.unionSets(1, 2);  // 合并为 {0,1,2}, {3}, {4}
    uf.unionSets(3, 4);  // 合并为 {0,1,2}, {3,4}

    std::cout << "0 和 2 是否连通？ " << uf.connected(0, 2) << "\n";  // 输出1（true）
    std::cout << "1 和 3 是否连通？ " << uf.connected(1, 3) << "\n";  // 输出0（false）

    return 0;
}

六、应用场景

1. 图论算法

   • Kruskal算法中的边排序与环检测。
   • 判断无向图的连通分量。

2. 动态连通性问题

   • 社交网络中快速判断两人是否间接好友。
   • 棋盘游戏中区域连通性检测。

3. 网络连接管理

   • 服务器集群的故障恢复与动态分组。

七、常见问题与解决方案

1. 路径压缩导致秩不准确？
   秩（按树高合并时）在路径压缩后可能不再精确反映树高，但合并方向仍能保持低树高特性。

2. 元素数量动态变化？
   需使用哈希表替代数组，支持动态元素插入（C++中可用 std::unordered_map）。

3. 需要统计集合大小？
   额外维护一个 size[] 数组，在合并时更新大小。

八、扩展实现（按大小合并）

class UnionFind {
private:
    std::vector<int> parent;
    std::vector<int> size;  // 记录集合大小

public:
    UnionFind(int n) : parent(n), size(n, 1) {
        for (int i = 0; i < n; ++i) parent[i] = i;
    }

    int find(int u) {
        if (parent[u] != u) {
            parent[u] = find(parent[u]);
        }
        return parent[u];
    }

    bool unionSets(int u, int v) {
        int rootU = find(u);
        int rootV = find(v);
        if (rootU == rootV) return false;

        // 小集合合并到大集合
        if (size[rootU] < size[rootV]) {
            parent[rootU] = rootV;
            size[rootV] += size[rootU];
        } else {
            parent[rootV] = rootU;
            size[rootU] += size[rootV];
        }
        return true;
    }
};