并查集（Union-Find）

并查集是一种用于处理 动态连通性问题 的数据结构，常用于解决「图的连通性」相关问题。它支持两种操作：

1. 合并（Union）：将两个集合合并为一个集合。
2. 查找（Find）：找到某个元素所属集合的代表（根节点）。

>[!warning] >并查集无法以较低复杂度实现集合的分离。

---

并查集的核心思想

并查集通过树形结构表示集合：

1. 每个集合用一棵树表示，每个节点指向它的父节点。
2. 树的根节点是集合的代表。
3. 每个集合可以通过其根节点唯一标识。

并查集的操作通过两个关键函数实现：

• Find(x)：找到元素 x 所属集合的根节点。
• Union(x, y)：将包含 x 和 y 的两个集合合并为一个集合。

---

并查集的实现

并查集可以用以下方式优化实现：

1. 基本实现

• 用数组表示集合，parent[i] 表示节点 i 的父节点。
• 初始时，每个节点的父节点是它自身。

2. 路径压缩优化

• 在查找时，将树的深度减小，使得树扁平化，从而加速后续操作。
• 当执行 Find(x) 时，将xx 到根节点路径上的所有节点直接指向根节点。

3. 按秩合并优化

• 在合并两个集合时，总是将较小的树（秩低的树）合并到较大的树（秩高的树）中，从而减少树的高度。

4. 路径压缩 + 按秩合并

• 结合路径压缩和按秩合并的优化，可以将并查集的操作时间复杂度优化为几乎常数 $O(\alpha (n))$，其中 $\alpha (n)$ 是反阿克曼函数，增长非常缓慢。

---

并查集的常见操作

1. 初始化

初始化时，每个元素各自为一个集合，每个节点的父节点指向自身：

parent = [i for i in range(n)]  # n 是元素的数量
rank = [1] * n  # 初始化每个节点的秩为 1

2. 查找操作（Find）

查找某个元素所在集合的根节点：

• 我们需要沿着树向上移动，直至找到根节点。

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

3. 合并操作（Union）

合并两个集合（按秩合并）：

• 要合并两棵树，我们只需要将一棵树的根节点连到另一棵树的根节点。

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_y] = root_x
        elif rank[root_x] < rank[root_y]:
            parent[root_x] = root_y
        else:
            parent[root_y] = root_x
            rank[root_x] += 1  # 增加根节点的秩

---

并查集的时间复杂度

• 在路径压缩和按秩合并的优化下，并查集的时间复杂度为：
  • 单次操作：$O(\alpha (n))$，其中$\alpha (n)$ 是反阿克曼函数。
  • 由于反阿克曼函数增长极慢，在实际应用中可以认为 $O(\alpha (n))\approx O(1)$。

---

并查集的应用场景

1. 图的连通性问题

• 判断无向图中两个节点是否连通。
• 如：判断一个图是否是树。

2. 最小生成树（Kruskal算法）

• 在 Kruskal 算法中使用并查集判断边是否属于同一个连通分量，从而决定是否加入生成树。

3. 动态连通性问题

• 解决动态添加边后的连通性问题。

4. 网络中节点连通性

• 如：判断社交网络中的两人是否属于同一社交群体。

5. 岛屿问题

• 计算二维网格中的岛屿数量。

---

示例代码

以一个图的连通性问题为例，判断是否两个节点连通：

# 并查集实现
class UnionFind:
    def __init__(self, n):
        self.parent = [i for i in range(n)]  # 初始化，每个节点指向自己
        self.rank = [1] * n  # 秩初始化为 1

    # 查找操作，带路径压缩
    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 = self.find(x)
        root_y = self.find(y)
        if root_x != root_y:
            if self.rank[root_x] > self.rank[root_y]:
                self.parent[root_y] = root_x
            elif self.rank[root_x] < self.rank[root_y]:
                self.parent[root_x] = root_y
            else:
                self.parent[root_y] = root_x
                self.rank[root_x] += 1

# 示例：判断图的连通性
n = 5  # 节点数
edges = [(0, 1), (1, 2), (3, 4)]  # 图中的边
uf = UnionFind(n)

# 合并所有的边
for x, y in edges:
    uf.union(x, y)

# 判断两个节点是否连通
print(uf.find(0) == uf.find(2))  # True，0 和 2 是连通的
print(uf.find(0) == uf.find(4))  # False，0 和 4 不连通

---

总结

并查集是一种高效解决动态连通性问题的经典数据结构，其性能通过路径压缩和按秩合并优化，广泛用于图论算法（如Kruskal）和各种实际问题（如连通性、岛屿问题等）。