并查集基础学习笔记

什么是并查集？

并查集是一种树型的数据结构，用于处理一些不相交集合（Disjoint Sets）的合并及查询问题。常常在使用中以森林来表示。

并查集的特点

并查集有三个重要操作：

1. 初始化：makeSet()

将每个元素初始化成一个单独的集合。

2. 查找：find()

查找元素所在的集合，即根节点。

3. 合并：union()

将两个集合合并成一个集合。

使用并查集可以快速地回答两个元素是否在一个集合中，以及将两个集合合并成一个集合。并查集在实现上使用了路径压缩和按秩合并等优化方法，使得使用并查集的时间复杂度为 O(α(n))，其中α(n) 是阿克曼函数的反函数，增长极慢。

并查集的实例

下面给出一个示例，假设我们有五个元素 {0, 1, 2, 3, 4}，需要将它们分为两个集合 {0, 1, 2} 和 {3, 4}，并查询两个元素是否在同一集合中。

初始情况下，每个元素自成一个集合：

Copy Code
0   1   2   3   4  
|   |   |   |   |  
0   1   2   3   4  

然后我们将 {0, 1, 2} 合并成一个集合，得到：

Copy Code
0   1   2   3   4  
 \ / \ /   |   |  
  0   1     2   3   4  

最后我们查询 0 和 3 是否在同一集合中，查询过程如下：

Copy Code
0   1   2   3   4  
 \ / \ /   |   |  
  0   1     2   3   4  

find(0) = 0  
find(3) = 3  

可知 0 和 3 不在同一集合中。