含义

主要解决一些分组、判断成环、两个元素是否存在某种关系等问题。
注意，说到的这些集合，是不相交集合。
合并（union）：两个不相交的集合合并成一个。
查询（find）：查询两个元素是否在同一集合中。

步骤：

1、初始化时，一个元素代表一个集合，合并时，要合并的节点指向另一个节点；
2、要合并时，找出两个要合并节点的根节点，根据根节点是否相同来判断两个元素是否属于同一集合，若不属于同一集合（即根节点不同），则将要合并的节点的根节点，指向另一节点的根节点。

结构

其结构实际上是个树，其根节点就是集合的代表元素。

路径压缩

合并过程中， 可能会生成一条长链，导致查询根节点的时间变长，所以希望每个节点到根节点的路径尽可能短些，解决方法就是：把查询过程中，沿途经过每个节点的父节点，都设置成根节点，用递归实现。

比较方法

把简单的树往复杂树上合并，使得合并后到根节点距离变长的节点个数较少。

时间复杂度

查询次数*合并次数

实现

1、quick find

顾名思义，查询快、合并慢，

如果要union(1,6)，是不同集合，合并后，之前分别跟1连接的元素、跟5连接的元素，也都连接起来了。
查询的时间复杂度O(1)，合并复杂度O(n)。
当数据量变大后，因为O(n)，所以变慢，接下来就优化一下这部分。

2、quick union

使用树形结构来描述，用数组来存储。
合并和查询时间复杂度都是O(h)，h是树的高度，相比quick find，quick union是牺牲了部分查找性能，提高合并性能。
测试发现，数据量小的时候quick union性能明显优于quick find，但当数据量一大起来，却明显差于quick find，因为quick union的查询、合并时间复杂度始终是O(h)，生成的树深度可能很深。
接下来，我们试试优化。