并查集（Union-Find）数据结构

并查集是一种用于处理不相交集合（Disjoint Sets）合并与查询问题的数据结构。它支持两种操作：合并两个集合（Union）和查询元素所属集合（Find）。其核心应用包括判断图中两个节点是否连通、最小生成树算法（如Kruskal算法）等。

1. 基本概念与表示方法

想象有若干个元素，最初每个元素都属于自己的独立集合。我们可以用一棵树来表示一个集合，树的根节点作为该集合的“代表元”。并查集的核心思想是：判断两个元素是否属于同一个集合，只需要看它们的根节点是否相同。

初始状态下，有n个元素（例如0到n-1），我们可以用一个长度为n的数组parent来表示。parent[i]存储的是元素i的父节点。初始时，每个元素都是独立的，所以parent[i] = i，即每个元素都是自己所在集合的根。

2. 核心操作：Find（查询）

Find操作的目标是找到给定元素所在集合的根节点（代表元）。

步骤：

1. 输入一个元素x。
2. 从x开始，沿着parent数组向上查找，即不断访问x = parent[x]。
3. 直到找到parent[x] == x的元素，这个x就是根节点。
4. 返回这个根节点。

示例：
假设我们有集合{0, 1, 2, 3}，初始parent = [0, 1, 2, 3]。

• Find(0) -> 路径：0 -> 0，返回0。
• Find(3) -> 路径：3 -> 3，返回3。

3. 核心操作：Union（合并）

Union操作的目标是将两个元素所在的集合合并成一个集合。

基本步骤：

1. 分别找到元素x和元素y的根节点（使用Find操作），记作rootX和rootY。
2. 如果rootX == rootY，说明x和y已经在同一个集合中，无需合并。
3. 如果rootX != rootY，则将其中一个根节点指向另一个根节点。例如，将parent[rootY]设置为rootX。这样，两棵树就合并成了一棵。

示例：
初始parent = [0, 1, 2, 3]。

• 执行Union(1, 2)：
  • Find(1)返回1，Find(2)返回2。
  • 将parent[2]设置为1。现在parent = [0, 1, 1, 3]。集合变为{0}, {1, 2}, {3}。
• 再执行Union(2, 3)：
  • Find(2)：2 -> parent[2]=1 -> 1 (parent[1]=1)，返回1。
  • Find(3)返回3。
  • 将parent[3]设置为1。现在parent = [0, 1, 1, 1]。集合变为{0}, {1, 2, 3}。

4. 优化策略：路径压缩（Path Compression）

在基础的Find操作中，如果树变得很高（例如退化成一条链），每次Find操作都需要遍历整条路径，效率会很低（最坏情况O(n)）。

路径压缩是一种优化技巧，它在Find操作的过程中，顺便将路径上的所有节点的父节点都直接指向根节点。这样，后续对同一路径上节点的查找会变得非常快。

优化后的Find操作步骤：

1. 如果parent[x] != x，说明x不是根节点。
2. 递归地（或迭代地）找到根节点root。
3. 在递归返回的过程中，将路径上每个节点x的父节点直接设置为root (parent[x] = root)。
4. 返回root。

示例：
假设有parent = [0, 0, 1, 2]，结构是0 <- 1 <- 2 <- 3。

• 执行Find(3)（优化后）：
  • Find(3)调用Find(2)。
  • Find(2)调用Find(1)。
  • Find(1)调用Find(0)，0是根，返回0。
  • 在Find(1)返回前，设置parent[1] = 0。
  • 在Find(2)返回前，设置parent[2] = 0。
  • 在Find(3)返回前，设置parent[3] = 0。
• 操作后，parent变为[0, 0, 0, 0]。所有节点都直接指向根节点0。

5. 优化策略：按秩合并（Union by Rank）

在基础的Union操作中，我们随意地将一棵树合并到另一棵树上。这可能导致树的高度增长过快，甚至退化成链。按秩合并是另一种优化，它总是将“较小”的树（高度较低的树）合并到“较大”的树（高度较高的树）的根节点上，以控制树的高度增长。

实现方法：

• 我们需要一个额外的数组rank，rank[i]记录以i为根节点的树的高度的近似值（秩）。
• 初始时，每个元素的rank为0。
• 合并时，比较两个根节点的rank：
  • 如果rank[rootX] > rank[rootY]，将rootY的父节点设为rootX。
  • 如果rank[rootX] < rank[rootY]，将rootX的父节点设为rootY。
  • 如果rank[rootX] == rank[rootY]，任意将一棵树合并到另一棵，并将新根的rank加1（因为两棵树高度相同，合并后高度会增加1）。

示例：
初始parent = [0, 1, 2, 3], rank = [0, 0, 0, 0]。

• Union(1, 2)：rank[1]==0, rank[2]==0，相等。假设将2合并到1，parent[2]=1。rank[1]需要加1，变为1。parent = [0, 1, 1, 3], rank = [0, 1, 0, 0]。
• Union(2, 3)：Find(2)找到根1 (rank=1)，Find(3)找到根3 (rank=0)。rank[1] > rank[3]，将3合并到1，parent[3]=1。rank不变。parent = [0, 1, 1, 1], rank = [0, 1, 0, 0]。

6. 完整实现与复杂度分析

结合路径压缩和按秩合并，并查集的效率非常高。

伪代码/简化实现：

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):
        rootX = self.find(x)
        rootY = self.find(y)
        if rootX == rootY:
            return
        # 按秩合并
        if self.rank[rootX] < self.rank[rootY]:
            self.parent[rootX] = rootY
        elif self.rank[rootX] > self.rank[rootY]:
            self.parent[rootY] = rootX
        else:
            # 秩相等，任意合并，新根秩+1
            self.parent[rootY] = rootX
            self.rank[rootX] += 1

复杂度分析：

• 在同时使用路径压缩和按秩合并的情况下，并查集每个操作的平均（摊还）时间复杂度接近于O(α(n))。
• 其中α(n)是反阿克曼函数，其增长极其缓慢，对于所有实际应用场景（n远小于宇宙原子数），α(n)通常小于5。
• 因此，并查集的操作可以被认为是近乎常数时间的。

总结：
并查集通过树形结构表示集合，核心操作是Find和Union。通过路径压缩和按秩合并两大优化，其效率变得极高，是解决动态连通性等问题的利器。理解其原理和优化策略是掌握该知识点的关键。