并查集一般解决的是对于给定的多个集合之间的合并和查询问题，假设我们现在有n个集合，每个集合都有一个独立的编号，我们对这些初始集合进行n次合并操作（每次将两个集合合并成一个），然后进行m次询问，查找两个元素是否在同一个集合之中。

我们实现并查集的方法大致分为两种：1.Quick Find方法，2.Quick Union方法。

1.Quick Find并查集的基本思想：
QuickFind并查集是一种高速查找的并查集，它的基本思想很简单，假设我们现在有一些元素。

我们让每个元素都直接标记他们所属的集合编号，比如左边的图里每个元素都属于集合X，右边的图里每个元素都属于集合Y，这样的话我们无论访问哪个元素都可以以O（1）的速度知道他们所在的集合。

但是很显然，我们如果想要合并两个结合就不那么容易了。

我们需要把属于一个集合里的所有元素的标记都更改为另一个集合的编号才能完成合并。

这样就会在合并两个集合的时候花费很多时间，在有些合并集合次数比较多的时候，这种并查集的实现方法往往是不适用的。

2.Quick Union并查集的基本思想：
为了解决QuickFind并查集合并集合的速度问题，设计出了QuickUnion并查集算法

QuickUnion并查集用树形来维护一个集合的元素信息

我们随机用一个树来构成一个集合。
而我们如果此时有两个集合，我们在合并时只需要将一个集合的根节点连接在另一个集合的根节点下即可。

这样，我们以一种简单的方式就把两个集合连接了起来，而不用进行复杂的修改操作。

但这时我们会发现，我们虽然在合并集合时省了不少的时间，但是我们在查询一个元素属于哪个集合的时候就没有那么简单了，下面让我们分析一下如何查找元素所在的集合编号。

为了给查找提供便利，我们不妨设一个集合根节点的父节点编号等于它自己。这样的话对于一个元素如果其父节点的编号的等于自己的话，就说明它是当前集合的根节点。

而非根节点元素，可以不断访问它的父节点上溯，最终找到它所在的集合的根节点，我们可以根据某个元素所在集合的根节点判断这个元素属于哪个集合。如果两个元素拥有共同的根节点的话，那么这两个元素就属于同一个集合。

这样的话我们的查找操作可能就达不到O（1）的速度。

但是我们注意到，每个集合是一个多叉树形结构，又因为每次合并集合的时候，我们是把另一个集合直接连接在一个集合的根节点上，所以我们树的深度其实并不会达到多高。

因此查找也不会耗费很长的时间，大约为O（LogN）的速度，这样的速度已经很快了，和常数差别不大。

这就是QuickUnion的基本思想。

3.Quick Union并查集的路径压缩：

我们发现，在查找一个元素所在集合的根节点时，肯定会访问这个元素到根节点中的一系列元素，所以我们为了避免在下次再次访问的时候还要重复这一操作，我们可以在一次查找操作找到根节点以后，将一路上访问的元素直接和根节点连接起来，这样在下次访问的时候，就能以O（1） 的速度找到这些元素的根节点了

我们需要在查找A所在集合的根节点时，访问了A->B->X，那么我们在这次访问找到根节点（X）以后，就把A，B直接连在X上，这样的话，我们下次查找A，或者B的时候就可以有更快的速度。

我们只需要程序支持两个操作即可，1.查找操作一个元素所在的集合的根节点，2.将两个元素所在的集合合并为一个集合。

int find(int x){
//返回x的祖宗节点
//加上路径压缩
if(p[x]!=x) p[x]=find(p[x]);
//每次如果当前节点不是根节点
//就递归寻找它父亲的根节点，顺便路径压缩
return p[x];
//如果找到了根节点的话就返回，更新先前的递归
}

这里我们的Find函数就完成了查找某个元素所在集合的根节点，在访问过程中进行了路径压缩。

这里P[x]表示的是x节点的父节点的编号。如果p[x]!=x就表示当前节点不是根节点，就递归寻找当前节点的父节点。

p[x]=find(p[x]); 操作可以在找到根节点返回后，将根节点的编号赋给p[x]，这样的话，路径上访问的所有点的p[x]都会直接指向根节点，这样就完成了路径压缩。

我们完成了Find操作以后，那么合并两个结合就变得简单很多，我们直接p[Find(a)]=Find(b)，就可以将a元素所在集合的根节点的父节点设置为b所在集合的根节点。这样就完成了两个集合的合并。

我们发现QuickUnion在加上路径压缩操作以后，查询的操作速度也达到近乎O（1）的速度，而合并两个集合的速度也是很快的。所以我们一般所说的并查集主要指的就是QuickUnion并查集。

https://zhuanlan.zhihu.com/p/434512805

https://blog.csdn.net/nobody_1/article/details/112715629

https://blog.csdn.net/wmy0217_/article/details/104972191