前言
今天在力扣上做了一道每日一题，接触到了并查集这个概念，以前没有了解过，记录在此。
定义
并查集(Disjoint-Set)是一种可以动态维护若干个不重叠的集合，并支持合并与查询两种操作的一种数据结构。
官方关于并查集的说明没有找到，但是并查集的概念那就是维护了一个森林，森林里有很多树，每棵树代表了一个集合，树的根节点就是这个集合的leader，树里面没个子节点都是这个集合的一个单元。
而这个森林支持两种操作
1、查询：给定一个目标值，找到这个目标值的leader
2、合并：给定两个目标值，把两个目标合并到一个集合中
操作是就这么两个操作，看起来很简单，接下来可以先简单的玩一下。
张三的老大是张二、张二的老大是张大，张大是leader，老大是自己；
李四的老大是李三，李三是leader，老大是自己；
查找
现在我们想查一下李四的老大是谁，步骤如下
1、李四是leader么？不是，找李四的老大
2、李四的老大是李三，李三是leader么？是，那么返回李三。
合并
case1：现在新来了一个李氏集团有一个新成员李五要加入。那么要把李五合并进李氏集团，步骤如下。
随便找一个李氏的成员，比如李四，让李四当上李五的老大，合并完成。
case2：现在张氏集团要把李氏集团整体收编
随便找一个张氏集团的成员，比如张二；
随便找到一个李氏集团的成员（任一成员的老大都是一个人），找到其老大，李三；
让张二当上李三的老大，合并完成。
与树的不同
其实根据上面的例子可以看出来，并查集每一棵树，我们是从下往上找的，而在树中，我们通常是从上至下来寻找到各个节点。
这样反查的好处，就是在做一些合并操作的时候代价比较小，比如现在我们有两个元素突然有了共同点，我们要把两个元素所在的树合并（比如case2中，张二突然发现和李四是同一个姥姥生的，现在要把族谱扩大了）。这时，如果要从上之下来找，我们要遍历森林里所有的书，才能知道这两个元素（张二和李四）分别所在的树在哪，然后再把两棵树合并，如果从下至上来查找，那么只需要让一个元素让另一个元素的老大就行了（修改父节点指针）
使用场景
通常并查集这种数据接口都用在多集合反向索引的场景，比如找亲戚
同学a有亲戚b、c、d
同学b有亲戚e、f
同学g有亲戚h、i
那么可以看到e、f通过b和a、c、d都建立起一个亲戚的关系，我们可以通过并查集，直接将两组集合合并，然后再判断两个人是否是亲戚的时候直接判断是不是在一个集合（是不是同一个老大），就可以了。
不然、假设我们要看c和f是不是亲戚，
1、我们要找到所有有c的集合，然后在这些集合看下是不是有f，
2、我们还要看下c所在的所有集合的所有成员所在的集合里是不是是有f
3、我们还要看c所在的所有集合的所有成员所在的所有集合里是不是有f....
周而复始，复杂度越来越大
所以并查集主要是用来解决这种多线索集合的问题，通常数据结构为一个网状（图），我们构建一个并查集（森林），维护这些集合（树）。
网友评论