编辑“︁并查集（Disjoint Set Union, DSU）”︁

= 并查集（Disjoint Set Union, DSU） =

'''并查集'''（Disjoint Set Union, DSU），也称为'''联合查找集'''（Union-Find），是一种用于管理元素分组的数据结构。它支持两种主要操作：  
* '''查找（Find）'''：确定某个元素属于哪个集合（通常返回该集合的“代表”元素）。  
* '''合并（Union）'''：将两个集合合并为一个集合。  

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

== 基本概念 ==

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

=== 示例 ===
假设有 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 实现，包含路径压缩和按秩合并优化：

<syntaxhighlight lang="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
</syntaxhighlight>

=== 输入与输出解释 ===
* 初始状态：`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 个人，其中一些人是朋友关系（朋友的朋友也是朋友）。求朋友圈的数量。

<syntaxhighlight lang="python">
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
</syntaxhighlight>

== 复杂度分析 ==
* 初始化：<math>O(n)</math>  
* 单次 `Find` 或 `Union`：<math>O(\alpha(n))</math>（接近常数时间）  
* 空间：<math>O(n)</math>  

== 可视化 ==
<mermaid>
graph TD
    0 --> 1
    2 --> 3
    0 --> 2
    4
</mermaid>
* 初始：5 个独立节点。  
* 合并后：{0, 1, 2, 3} 和 {4}。

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

[[Category:计算机科学]]
[[Category:数据结构与算法]]
[[Category:高级数据结构]]