并查集（Union-Find）数据结构的原理与实现

题目描述
并查集是一种用于管理元素分组情况的数据结构，支持两种操作：合并（Union）两个不相交集合，查询（Find）某个元素所属集合。它广泛应用于连通性判断、最小生成树等算法中。

核心概念

1. 每个集合用一棵树表示，树的根节点作为集合的代表元
2. 每个节点记录其父节点，根节点的父节点指向自己
3. 通过查找根节点判断两个元素是否属于同一集合

基础实现步骤

1. 初始化

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))  # 每个节点的父节点初始化为自己

2. 查找操作（未优化）

def find(self, x):
    while self.parent[x] != x:  # 循环直到找到根节点
        x = self.parent[x]
    return x

3. 合并操作（未优化）

def union(self, x, y):
    root_x, root_y = self.find(x), self.find(y)
    if root_x != root_y:
        self.parent[root_y] = root_x  # 将y的根节点接到x的根节点下

优化策略

4. 路径压缩优化
   在查找过程中将节点直接连接到根节点，降低树高度：

def find(self, x):
    if self.parent[x] != x:
        self.parent[x] = self.find(self.parent[x])  # 递归压缩路径
    return self.parent[x]

5. 按秩合并优化
   记录树的深度（秩），总是将小树合并到大树下：

def __init__(self, n):
    self.parent = list(range(n))
    self.rank = [0] * n  # 记录每棵树的深度

def union(self, x, y):
    root_x, root_y = self.find(x), self.find(y)
    if root_x == root_y:
        return
    # 按秩合并：小树合并到大树
    if self.rank[root_x] < self.rank[root_y]:
        self.parent[root_x] = root_y
    elif self.rank[root_x] > self.rank[root_y]:
        self.parent[root_y] = root_x
    else:
        self.parent[root_y] = root_x
        self.rank[root_x] += 1  # 深度相同时合并后深度+1

时间复杂度分析

• 未优化：最坏情况O(n)
• 仅路径压缩/按秩合并：O(log n)
• 两种优化结合：近似O(α(n))，α为反阿克曼函数，在实际应用中被视为常数时间

完整代码示例

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n
    
    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    
    def union(self, x, y):
        rx, ry = self.find(x), self.find(y)
        if rx == ry:
            return False
        if self.rank[rx] < self.rank[ry]:
            self.parent[rx] = ry
        elif self.rank[rx] > self.rank[ry]:
            self.parent[ry] = rx
        else:
            self.parent[ry] = rx
            self.rank[rx] += 1
        return True