高阶数据结构------并查集

并查集

在一些应用问题中，需要将n个不同的元素划分成一些不相交的集合。开始时，每个元素自成一个集合，然后按照一定的规律将归于同一组的元素集合合并。在此过程中要反复用到查询某一个元素归属于哪一个集合的运算。适合于描述这类问题的抽象数据结构类型成为并查集（UnionFindSet）。

比如：亲戚关系，朋友敌人关系，食物链关系。

比如：给定10个人，5对关系，没对关系描述两个人，表示这两个人是亲戚，最后问你某两个人之间是否是亲戚关系。

再比如：给定10个人，5对关系，没对关系描述两个人，表示这两个人之间的关系（朋友或者敌人），最后问你某两个人之间的关系。

…………

上述问题就可以使用并查集这一数据结构来解决。

接下来实现并查集这一数据结构

以一个简单的列子为例：

某公司今年校招全国总共招生10人，西安招4人，成都招3人，武汉招3人，10个人来自不

同的学校，起先互不相识，每个学生都是一个独立的小团体，现给这些学生进行编号：{0, 1, 2, 3,

4, 5, 6, 7, 8, 9}; 给以下数组用来存储该小集体，数组中的数字代表：该小集体中具有成员的个

数。(负号下文解释)

毕业后，学生们要去公司上班，每个地方的学生自发组织成小分队一起上路，于是：

西安学生小分队s1={0,6,7,8}，成都学生小分队s2={1,4,9}，武汉学生小分队s3={2,3,5}就相互认识

了，10个人形成了三个小团体。假设右三个群主0,1,2担任队长，负责大家的出行。

一：初始化

起初时，我们可以创建一个数组，数组下标表示元素的编号，数组中的值全部初始化为-1，表示该元素最初子集单独为一个集合（自己就是父亲）。

二：Find操作

该操作的目的是判断某个元素属于哪个集合（找到该元素所属集合的代表元素（通俗来说就是向上找跟操作））。

该操作可以通过循环来实现，不断去找自己的父亲，不断向上走，知道最终的元素没有父亲（值为-1）为止。

三：Union操作

已知两个元素之间存在关系要合并这两个元素，本质是将这两个元素所属的集合进行合并，这很好理解，朋友的朋友还是朋友。因此要先进行找两个元素所属集合的根节点，最终将这两个集合合并（一个集合的根节点认另一个集合的根节点为父亲）

顺便可以统计一下合并后集合共有多少元素（abs(_ufs[root1])）

四：ISsame操作

给定两个元素，判断这两个元素是否属于同一个集合。

只需要判断这两个集合的祖先是否相同就可以了。

五：SetCount操作

判断当前一共有多少个集合（有多少个大家庭）

只需要遍历一遍数组，判断有多少值为-1就可以了。

并查集优化操作

一般来说并查集实现成上面的样子已经可以了，但是当数据量比较庞大的时候，效率（性能）

就会有所下降，因此要考虑进行优化。

一：优化Union操作

在上面实现的并查集中，采用的方法是将下标大的元素向下标小的元素合并，极端情况下经过一系列合并后集合会成为一个链表结构（一条线），再进行Find操作时时间复杂度就会是O(n)。

因此，我们改变合并思路，我们每次进行合并操作时，都将元素数量少的集合向元素数量多的集合合并，这样就可以很好的控制集合这一树形结构的高度，性能就会有所提升。

二：路径压缩

并查集只是要在某一个集合中找出一个代表元素，并不在意找出哪一个，因此对于不是根的结点，

认谁为父亲都是可以的，因此我们在Find操作的过程中就可以进行路径压缩，将所有遍历到的结点

的父亲都修改成root，这样可以大大降低树的高度，查找的时间复杂度近似为O(1),性能就会提升。

路径压缩也可以实现成递归的形式（代码短，好写），但是不太推荐，递归怕的就是层数太深，

如果数据量非常大的情况下递归很可能是不可行的。