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

题目描述
并查集（Union-Find）是一种用于管理元素分组情况的数据结构，支持两种操作：

1. 合并（Union）：将两个元素所在的集合合并为一个集合。
2. 查找（Find）：查询某个元素所属的集合（通常用集合的“代表元”标识）。

并查集常用于解决动态连通性问题，例如：

• 网络中的节点连通性判断
• 最小生成树算法（Kruskal）
• 社交网络中的好友关系

解题过程循序渐进讲解

步骤1：核心思想
每个集合用一棵树表示，树的根节点作为集合的“代表元”。

• 初始时，每个元素自成一个集合（即自己是根）。
• 合并时，将一个集合的根指向另一个集合的根。
• 查找时，沿着父指针找到根节点。

步骤2：数据结构设计
使用数组 parent[] 表示每个节点的父节点：

• 初始：parent[i] = i（每个节点都是根）
• 查找根：递归或迭代地找 parent[i] == i 的节点

示例（5个元素）：
初始：parent = [0,1,2,3,4]

步骤3：基本操作实现

3.1 查找（Find）
查找元素 x 的根（代表元）：

def find(x):
    while parent[x] != x:
        x = parent[x]
    return x

问题：树可能退化成链，查找效率低（O(n)）。

3.2 合并（Union）
将元素 x 和 y 所在集合合并：

def union(x, y):
    root_x = find(x)
    root_y = find(y)
    if root_x != root_y:
        parent[root_x] = root_y  # 将 root_x 的父节点设为 root_y

问题：随意合并可能使树更高，降低效率。

步骤4：优化策略

4.1 按秩合并（Union by Rank）

• 用数组 rank[] 记录每个根的树高（初始为0）。
• 合并时，将矮树的根指向高树的根（避免树增高）。

def union(x, y):
    root_x = find(x)
    root_y = find(y)
    if root_x != root_y:
        if rank[root_x] < rank[root_y]:
            parent[root_x] = root_y
        elif rank[root_x] > rank[root_y]:
            parent[root_y] = root_x
        else:
            parent[root_y] = root_x
            rank[root_x] += 1  # 两树同高，合并后高度+1

4.2 路径压缩（Path Compression）
查找过程中，将沿途节点的父节点直接设为根：

def find(x):
    if parent[x] != x:
        parent[x] = find(parent[x])  # 递归压缩
    return parent[x]

或迭代版本：

def find(x):
    # 先找到根
    root = x
    while parent[root] != root:
        root = parent[root]
    # 路径压缩
    while parent[x] != root:
        parent[x], x = root, parent[x]
    return root

效果：结合两种优化，每次操作平均时间复杂度接近 O(α(n))，其中 α(n) 是反阿克曼函数，增长极慢，可视为常数时间。

步骤5：完整代码示例

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):
        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
    
    def connected(self, x, y):
        return self.find(x) == self.find(y)

步骤6：应用示例
题目：给定节点 0~4，依次执行操作：

1. union(0,1)
2. union(2,3)
3. union(0,3)
   问：connected(1,3) 是否为 true？

执行过程：

• 初始：parent=[0,1,2,3,4], rank=[0,0,0,0,0]
• union(0,1)：0和1同秩，0为根，1指向0，rank[0]变为1 → parent=[0,0,2,3,4]
• union(2,3)：2和3同秩，2为根，3指向2，rank[2]变为1 → parent=[0,0,2,2,4]
• union(0,3)：找根(0)=0，找根(3)=2，rank[0]=1, rank[2]=1，0为根，2指向0，rank[0]变为2 → parent=[0,0,0,2,4]
• find(1)=0, find(3)=0 → connected 返回 true

总结

• 并查集的核心是树形结构+路径压缩+按秩合并。
• 优化后接近常数时间复杂度，适合大规模动态连通问题。
• 典型应用：Kruskal算法、朋友圈问题、岛屿数量动态计算等。