并查集（Disjoint Set Union, DSU）[编辑 | 编辑源代码]

并查集（Disjoint Set Union, DSU），也称为联合查找集（Union-Find），是一种用于管理元素分组的数据结构。它支持两种主要操作：

查找（Find）：确定某个元素属于哪个集合（通常返回该集合的“代表”元素）。
合并（Union）：将两个集合合并为一个集合。

并查集的高效实现通常使用路径压缩和按秩合并优化，使得这两种操作的时间复杂度接近常数（ $O (α (n))$ ，其中 $α (n)$ 是反阿克曼函数）。

基本概念[编辑 | 编辑源代码]

并查集的核心思想是将元素组织为树形结构，每个集合由一棵树表示，树的根节点是该集合的“代表”。初始时，每个元素自成一个集合（即每个元素的父节点是它自己）。通过合并操作，树的根节点会逐渐连接起来。

示例[编辑 | 编辑源代码]

假设有 5 个元素：0, 1, 2, 3, 4。初始时，每个元素的父节点是自己： ``` parent = [0, 1, 2, 3, 4] ```

执行 `Union(0, 1)` 和 `Union(2, 3)` 后，树结构变为： ``` parent = [0, 0, 2, 2, 4] ``` 此时集合为：{0, 1}, {2, 3}, {4}。

再执行 `Union(1, 3)`，集合变为 {0, 1, 2, 3}, {4}。

实现[编辑 | 编辑源代码]

以下是并查集的 Python 实现，包含路径压缩和按秩合并优化：

class UnionFind:
    def __init__(self, size):
        self.parent = list(range(size))
        self.rank = [0] * size  # 按秩合并优化

    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:
            return  # 已经在同一集合
        # 按秩合并
        if self.rank[root_x] > self.rank[root_y]:
            self.parent[root_y] = root_x
        else:
            self.parent[root_x] = root_y
            if self.rank[root_x] == self.rank[root_y]:
                self.rank[root_y] += 1

# 示例用法
uf = UnionFind(5)
uf.union(0, 1)
uf.union(2, 3)
uf.union(1, 3)
print(uf.parent)  # 输出: [0, 0, 0, 2, 4]
print(uf.find(3)) # 输出: 0

输入与输出解释[编辑 | 编辑源代码]

初始状态：`parent = [0, 1, 2, 3, 4]`
执行 `Union(0, 1)`：`parent = [0, 0, 2, 3, 4]`
执行 `Union(2, 3)`：`parent = [0, 0, 2, 2, 4]`
执行 `Union(1, 3)`：`parent = [0, 0, 0, 2, 4]`（路径压缩后）
`Find(3)` 返回 `0`，因为 3 的根是 0。

优化技术[编辑 | 编辑源代码]

路径压缩[编辑 | 编辑源代码]

在 `Find` 操作中，将节点的父节点直接指向根节点，从而 flatten 树结构，加快后续查询。

按秩合并[编辑 | 编辑源代码]

在 `Union` 操作中，将较小的树合并到较大的树下，避免树过高。秩（rank）是树高度的上界。

实际应用[编辑 | 编辑源代码]

并查集常用于解决以下问题： 1. 连通性问题：判断图中两个节点是否连通（如 Kruskal 算法中的最小生成树）。 2. 动态连通性：处理动态添加的边和查询。 3. 图像处理：像素连通区域标记。

案例：朋友圈问题[编辑 | 编辑源代码]

假设有 n 个人，其中一些人是朋友关系（朋友的朋友也是朋友）。求朋友圈的数量。

def count_circles(friendships, n):
    uf = UnionFind(n)
    for a, b in friendships:
        uf.union(a, b)
    # 统计不同根的数量
    roots = set(uf.find(i) for i in range(n))
    return len(roots)

friendships = [(0, 1), (1, 2), (3, 4)]
print(count_circles(friendships, 5))  # 输出: 2

复杂度分析[编辑 | 编辑源代码]

初始化： $O (n)$
单次 `Find` 或 `Union`： $O (α (n))$ （接近常数时间）
空间： $O (n)$

可视化[编辑 | 编辑源代码]

初始：5 个独立节点。
合并后：{0, 1, 2, 3} 和 {4}。

总结[编辑 | 编辑源代码]

并查集是一种高效处理动态连通性问题的数据结构，通过路径压缩和按秩合并优化，能够实现近乎常数的操作时间。它在图算法、网络连接分析等领域有广泛应用。