并查集定义：
并查集是一种树型的数据结构，用于处理一些不相交集合的合并及查询问题。常常在使用中以森林来表示。
并查集基本操作
并查集——Quick Find：
Quick Find
使用数组来表示存放集合的编号。
Quick Find 成员变量
Quick Find初始化：
Quick Find初始化
Quick Find的查询：
由于是数组存储每个集合的编号，所以查询操作的时间复杂度为O(1)。
find
Quick Find判断某两个元素是否同属于一个集合：
只需要判断 find(p) == find(q)即可。
isConnected
Quick Find的合并操作：
思路：分别找出元素p和元素q的所在的集合编号，如果两个集合编号不相等，说明需要合并。将其中一个集合转换为另一个集合的值。这里需要注意：Quick Find的合并操作的时间复杂度为O(n)。
union
所以，需要对Quick Find进行优化，下面我们使用树来表示一个集合。与其他树不同的是，每个节点指向的是父亲节点。
并查集—— Tree
使用树来表示一个集合。
并查集-树
并查集-树的结构
并查集-树的查询：
这里需要找到第 p 个元素的所在树的根节点，需要遍历，所以时间复杂度为O(h)，h 为树的高度。
find
并查集-树的合并：
直接让其中一个的树的根节点指向另一个数的根节点。此时，合并的时间复杂度为O(h)。
union
至此，并查集就是一个最优方案了吗？其实，并不是。在上面的合并操作中，有一个需要优化的地方，因为未考虑p 和 q 所在树的size,如果直接进行指向， 很可能让元素都在排成一个链表，增加了树的高度，从而影响了性能。所以，要让元素个数少的根节点指向元素个数大的根节点。如下图，操作union(0,2)，如果不对树的size进行比较，而直接让 0 元素的根节点 1 指向2，就成了一个链表。
合并前
合并后
并查集优化——size优化：
新增一个数组成员变量int[] sz，来保存每个集合的元素个数。
size优化-结构
新增sz成员变量之后，就可以根据p和q所在树集合的size大小来进行指向了。让元素个数少的树根节点指向元素个数大的树根节点。
size优化
至此，并查集就是一个最优方案了吗？其实，并不是。合并操作还可以再优化，这个也有一个缺点，那就是当一个宽度很大、深度很小的树 Tree1和 一个宽度很小、深度很大的树 Tree2进行合并，并且Tree1的size > Tree2的size，如果按照size 小的指向size大的原则， 则会把 Tree2头节点指向 Tree1的头节点，导致新的树 Tree1的深度增加了。更合理的合并策略是：深度低的树的根节点指向深度高的树的根节点。如下图，操作union(4,2)，如果不对树的深度进行比较，而是根据size进行比较，会让 4 元素的根节点 8 指向 2 元素的根节点 7，就成了一个深度更大的树结构。
合并前
合并后
并查集优化——rank优化：
将数组sz换成数组rank，以 根节点为下标，来表示该跟节点的树的排名（并不完全等于深度），这里说并不完全等于深度，后续会讲到。
rank优化-结构
根据 p 和 q 所在树的根节点，通过rank查找其树的深度，让深度低的树的根节点指向深度高的树的根节点。需要注意的是，当二者rank的值相等时，相当于要把其中一个树当成另一个树的子树，于是需要深度加1。
rank优化-合并
至此，并查集就是一个最优方案了吗？其实，并不是。查询操可以进行优化，我们的查找操作是通过p 元素，然后一层一层往上查找其根节点的；我们这里其实可以对从p遍历到根节点的路径进行压缩的，先执行 parent[p] = parent[parent[p]]，让 p 元素的父亲节点指向其爷爷。
并查集优化——路径压缩：
对某个节点到根节点的遍历路径进行压缩，实现方式是： parent[p] = parent[parent[p]]，让 p 元素的父亲节点指向其爷爷。
路径压缩
代码演示：
查询方法
这里对路径进行了压缩，但是并未影响rank的值，也就是说即使深度变小了，但是rank排名未变。
至此，并查集才算是一个比较完善的方案了。当然，我们还可以继续优化，就是把压缩路径一下子压缩到树的深度为2的终极情况。但是这样就需要递归处理这样的逻辑，如下图。
find-递归
由于是递归处理的逻辑，性能上较之前的循环处理要低一点，所以虽然结构上优于之前的树结构，但是总体的性能未必会优于之前的处理。
网友评论