并查集

在很多问题中，我们需要动态地维护一些元素之间的关系，例如：

• 两个点是否属于同一个集合
• 多次合并集合
• 判断元素之间是否“连通”

这类问题如果每次都重新遍历或搜索，会导致效率很低。
并查集 正是一种用来高效处理 集合合并与查询 的数据结构。它的核心价值在于能够动态管理元素的分组，并快速回答两个元素是否属于同一集合。

并查集通过维护一个树形结构来实现其功能，其中每个集合由一棵树代表。它主要支持两种操作：“查找”与“合并”。“查找”操作用于追溯一个元素所在集合的根代表，从而判断两个元素是否同属一组；“合并”操作则将两个独立的集合连接在一起。

它的卓越优势在于近乎常数时间的惊人效率。通过“路径压缩”和“按秩合并”两大优化策略，并查集能够将树结构保持得极其扁平，使得每次操作的平均时间复杂度接近 O(1)。这使其在解决连通性问题上无可替代，例如网络连接、朋友圈关系或图论中的最小生成树算法，都离不开它的高效支撑。

最小生成树是指在一个加权无向图中，找到一个边的子集，使得这些边能够连接图中的所有顶点（即形成一棵树），且总权重最小。最小生成树在通信网络设计、交通网络规划等领域有广泛的应用。

并查集主要用于在最小生成树 $Kruskal$ 算法中判断边的连接情况，确保不会形成环路，从而保证生成的树是连通且无环的。

---

1. 并查集的基本思想

并查集用于维护若干个 不相交集合，支持两种最基本的操作：

• 查找（Find）：查询某个元素属于哪个集合
• 合并（Union）：将两个集合合并成一个集合

在最初状态下，每个元素都单独属于一个集合。

假设一共有 $n$ 个元素，那么初始时可以表示为：

$$\{1\}, \{2\}, \{3\}, \dots, \{n\}$$

这表示每个元素彼此之间互不相关。

随着操作的进行，不同的集合会不断被合并，例如：

$$\{1,2,3\}, \{4,5\}, \{6\}$$

此时，集合的数量减少，但集合内部的元素数量变多。

---

2. 并查集的表示方式

并查集通常使用 一维数组 来实现。

我们用数组 fa[] 表示父节点关系，其中：

• fa[x] 表示 元素 $x$ 的父节点
• 如果 fa[x] = x，说明 $x$ 是当前集合的代表（根节点）
• 如果 fa[x] ≠ x，说明 $x$ 不是根节点，需要继续向上查找

初始化时，每个元素都作为一个独立集合存在，因此它的父节点就是自己：

for(int i = 1; i <= n; i++){
    fa[i] = i;
}

从数学意义上看，这个初始化状态可以表示为：

$$\forall x,\quad fa[x] = x$$

也就是说，任意元素 $x$，最开始都单独成集。

---

3. 查找操作（Find）

查找操作用于找到某个元素所在集合的代表元素，也称为根节点。

3.1 基本查找

int find(int x){
    if(fa[x] == x) return x;
    return find(fa[x]);
}

这段代码的含义是：

• 如果 $x$ 的父节点是自己，说明 $x$ 已经是根节点
• 否则继续向父节点查找，直到找到根节点为止

从集合的角度看，find(x) 的作用就是：

找到元素 $x$ 所在集合的唯一标识

用数学语言描述为：

$$\text{find}(x) = \text{集合中唯一的代表元素}$$

同一个集合中的所有元素，find 的结果一定是相同的。

---

3.2 路径压缩优化

如果多次合并后，集合结构变成一条很“深”的链，那么查找效率会下降。

路径压缩 的思想是：
在查找根节点的过程中，把中间经过的所有节点直接连接到根节点上。

int find(int x){
    if(fa[x] != x)
        fa[x] = find(fa[x]);
    return fa[x];
}

这样做的效果是：

• 查找一次后，路径变短
• 多次操作后，树的高度会大大降低

虽然路径压缩会改变内部结构，但不会改变集合的划分结果。

---

4. 合并操作（Union）

合并操作用于将两个元素所在的集合合并成一个集合。

4.1 基本合并

void unite(int x, int y){
    int fx = find(x);
    int fy = find(y);
    if(fx != fy){
        fa[fx] = fy;
    }
}

合并操作的逻辑步骤为：

1. 分别找到 $x$ 和 $y$ 所在集合的根节点
2. 如果两个根节点不同，说明它们属于不同集合
3. 将其中一个根节点指向另一个，完成集合合并

合并完成后，从集合关系上看，满足：

$$\text{find}(x) = \text{find}(y)$$

也就是说，$x$ 和 $y$ 已经属于同一个集合。

---

4.2 合并的本质

并查集在合并时，并不关心集合内部元素的顺序或结构，只关心：

• 元素是否在同一集合中
• 两个集合是否已经连通

因此，合并操作的时间复杂度非常低，只需要修改一个父节点即可。

---

5. 判断是否属于同一集合

判断两个元素是否在同一个集合中，是并查集中最常见的操作之一。

实现方式非常简单：

if(find(x) == find(y)){
    // x 和 y 在同一集合
}
else{
    // x 和 y 不在同一集合
}

从逻辑关系上，可以表示为：

$$x \sim y \iff \text{find}(x) = \text{find}(y)$$

其中 $x \sim y$ 表示 $x$ 与 $y$ 属于同一集合。

---

6. 并查集的常见应用

6.1 连通性判断

并查集常用于解决“是否连通”的问题，例如：

• 判断图中两个点是否连通
• 动态加入边后查询连通情况

unite(u, v);            // 添加一条边
find(x) == find(y);    // 判断是否连通

---

6.2 等价关系维护

并查集非常适合维护 等价关系，例如：

• 好友关系
• 同一阵营
• 属于同一类别

等价关系满足：

• 自反性
• 对称性
• 传递性

并查集的合并操作正好天然支持 传递合并。

---

6.3 最小生成树（Kruskal）

在 Kruskal 算法中，每次尝试加入一条边时，需要判断：

• 加入这条边是否会形成环

判断方式正是检查两个端点是否已经在同一集合中：

$$\text{find}(u) == \text{find}(v)$$

如果相等，说明已经连通，加入会形成环。
如果不等，则可以安全合并。

---

7. 常见错误与注意事项

1. 忘记初始化父节点数组

fa[i] = i; // 必须执行

2. 合并时未先查找根节点

fa[x] = y; // 错误写法

3. 下标范围不统一

如果元素编号从 $1$ 开始，数组大小必须相应扩大。

---

总结

并查集是一种用于维护 不相交集合 的高效数据结构，核心思想非常简单：

• 用数组记录父节点关系
• 用查找操作确定所属集合
• 用合并操作建立集合之间的联系

只要问题本质是：

集合合并 + 是否同属判断

就应当优先考虑使用并查集。