整个1月LeetCode很多题都是用并查集来解决的，这里记录下自己理解的并查集思路，方便以后查阅
本月做过属于并查集的题有：
2021/01/31 每日一题 相似字符串组
2021/01/30 每日一题 水位上升的泳池中游泳
2021/01/29 每日一题 最小体力消耗路径
2021/01/25 每日一题 由斜杠划分区域
2021/01/23 每日一题 连通网络的操作次数
2021/01/13 每日一题 冗余连接
2021/01/15 每日一题 移除最多的同行或同列石头
2021/01/11 每日一题 交换字符串中的元素
2021/01/07 每日一题 省份数量
以上基本上都是中等或困难难度的题，可以点击对应文章链接去看解题思路。
其实刚开始觉得为什么都是并查集感觉好烦，但是静下心来，这个月做了快10道并查集的题目，到今天31号的时候，看到并查集还是做起来挺轻松的了，LeetCode一个月并查集做下来还是挺有收获的。
所以并查集到底是什么？
并查集，在一些有N个元素的集合应用问题中，我们通常是在开始时让每个元素构成一个单元素的集合，然后按一定顺序将属于同一组的元素所在的集合合并，其间要反复查找一个元素在哪个集合中。
合并（Union）：把两个不相交的集合合并为一个集合。
查询（Find）：查询两个元素是否在同一个集合中。
基本上如果有多个节点要连接，查询他们是否连通/是否为一个集合的时候就能用到并查集，并查集的图解过程如下
创建节点
第一步就是创建多个节点，并且将节点自己的parent属性设定为自己，图中的箭头就代表着节点parent属性的指向
连接节点
之后通过传入的参数进行节点的链接，比如[1,5]、[1,2]、[5,3]
那么此时这个图自然分为了[1,2,3,5]/[4]/[6]/[7]/[8]，5个区域，其中[1,2,3,5]连通，这里就是合并的过程
一般程序中会将节点的parent属性设为另外一个节点，
[1,2]的连接比较好理解，直接把2节点的parent设为1节点即可，但是[1,5]和[5,3]是一个多点连接的线，是3>5>1的链接过程，当然可以5.parent = 1 3.parent = 5这样设置。
查询
对于并查集连接上了之后，要怎么样确定他们为同一个合集？
假设判断7和5是否为同一个合集：
7.parent属性是自己本身
5.parent属性是1，1.parent属性是本身
那么通过parent属性判断就能知道7/5不是一个合集
如果判断3/4是否连接
3.parent = 5 >5.parent = 1>1.parent = 1这样查询，最后返回的是1
4.parent = 4 返回的是4
1 !== 4 所以最后3/4没连接
通过上面的两个例子不难看出，在并查集里面最后来判断两个节点是否连通，都是通过parent属性不断向上查找，直到找到最底层的parent属性，一层层向上寻找，来对比这个属性内存的值，相等就是连通，对于短的连接也许时间还不长，但是面对大数据就比较麻烦了，所以就有了压缩路径的处理
压缩路径
单看上面[1,2,3,5]，其实在连接[5,3]的时候只需要将
5.parent的值直接给3.parent即可，就是把连接最顶端的节点给新连上的节点的parent属性，那么这里会用到递归来找到最顶端的节点
const find = function (x) {
while(x !== x.parent) {
x = x.parent
}
return x
}
// 伪代码使用
3.parent = find(5)
当一个节点的parent属性为自身的时候他就是顶端，根据这个原理，只要一直查找节点的parent属性，直到parent属性等于自身，那么就是找到了顶端节点了，之后赋值即可，那么上面的图就可以优化如下
优化后，如果要查找3/8是否连通
就不需要
3.parent = 5 >5.parent = 1>1.parent = 1这样查找，直接是3.parent = 1 >1.parent = 1，1次就能到位，在大数据运算的时候就能省下时间。
基本上并查集就上面几个步骤
- 将所有节点合并成不同的区域，每个区域的节点的
parent都指向1个parent属性等于自己的节点，这个节点就是当前区域的顶点 - 比较2点是否连通，就看他们区域的顶点是否连通，通过不断查找
parent，直到找到parent属性等于本身的节点，比较两个节点，不相同就是不连通
参考文章
