1、有时候，并不关心数据之间的前后关系，也不关心数据的层次关系。一些确定元素只是单纯的聚集在一起，这样的元素聚集集合被称为集合。
当希望知道某个数据是否存在一个集合中，或者两个元素是否在同一个集合中时，就需要使用一些集合数据结构来维护聚合元素之间的关系。如并查集、Hash表等
2、在一些集合的应用问题中，常给出集合中各个元素之间直接或间接的联系，要求将这些元素分成几个集合，并要求反复查找一个元素在哪个集合中。问题看似简单，但由于这类问题一般数据规模较大，采用常规的实现方法在空间和时间上都难以达到信息学竞赛的要求，而解决这类问题的一种有效的方法就是使用并查集。
3、有了树结构的基础知识后，我们来思考这样一个问题。
有很多棵树，每棵树有自己的节点，这些树组成了一个森林。
我们进行多次询问，每次询问两个节点是否在同一棵树上。这个问题应该如何处理呢？
例如：我们询问 (20,21) 是否在同一棵树上？
我们可能会对每棵树做一个编号，然后对树进行 DFS ，为树的每个节点进行编号，之后处理每个询问时，我们只要比较 2 个节点的编号是否相同即可
如果在询问的过程中，我们还会对一些树进行合并，合并后重新询问。这个问题又该如何处理呢？
树的合并问题。我们可以暴力的把一棵树中所有节点的编号改成另一棵树的编号。
这个方法最坏情况的复杂度是 O(n2) ，即每次都将一个较大的树合并到较小的树上。
如果我们规定，每次将较小的树合并到较大的树上，那么算法的复杂度为 O(nlog(n))
，这个方法也叫做启发式合并，未来在其他结构的合并中也会用到。
并查集顾名思义，包括并和查 2 个部分，并（ union ）即合并两个集合（树），查（ search ）检查 2 个点是否在同一个集合（树）内。
实际上是对上述问题的路径压缩策略。
我们不需要做任何的预处理，每次查询的时候，我们从 2 个节点分别向他们的根结点走，如果最终根节点是同一个，则表明两个节点在同一棵树中，否则是不同的两棵树。
例如： 20 的根为 1 ， 21 的根为 2 ，所以不在同一棵树中。
由于这类查询的特殊性，我们对树的存储方式进行一下修改，不用保存每个节点有哪些子节点，转为只保存每个节点的父节点是谁，这样并不影响上面的查询过程，并且更为灵活。
在大部分情况下，从节点走到根是很快的。但存在极为特殊的情况，也就是说这棵树退化为一个链表，这样从节点到根的距离，最坏就是 n 。如果我们重复多次对这 2 个节点进行查询，那么算法是非常低效的。
既然是多次对同一对节点进行查询，我们是否可以把之前的结果记录下来呢？这样下次询问时就不必重走一遍，直接给出结果就好。简单来讲，我们直接将节点的父节点设为他的根节点即可，虽然改变了树的形态，但并不影响查询结果。
例如：将 20 的父节点设为 1 ， 21 的父节点设为 2
我们考虑对上面的方法做进一步的优化。除了将节点自己的父节点设为根节点，所有从节点到根的路径上的节点，我们都可以使用同样的方法，将他们的父节点设为根结点。
例如：将 20,16,10,4 的父节点设为 1，21,17,13,7 的父节点设为 2 。
我们将这个过程称为路径压缩。路径压缩有效的提高了并查集的效率。
那么如何解决树的合并呢？这个其实很简单，我们只需要将原来某棵树的根节点，修改为另一棵树的根节点即可。这样合并也是 O(1) 的。
以上就是带路径压缩的并查集的过程，下面动图演示了合并 0,7 两点的过程。
并查集的复杂度低于 O(nlog(n)) ，这部分内容我们会在后面继续讲解。
除了路径压缩，并查集还有一个重要的约束：按秩合并。
那么什么是并查集的按秩合并呢？
该方法使用秩（ rank ）来表示树高度的上界，在合并时，总是将具有较小秩的树根指向具有较大秩的树根。简单的说，就是总是将 rank 值小的作为子树，添加到 rank 值大的树中（这个 rank 可以近似看为树的高度）
如果我们在合并两棵树时没有任何限制，在某些数据下，并查集的复杂度很有可能降到 O(nlog(n))
例如下图这种情况：
第一次合并大的集合和绿色这个点，之后查询红点，红点路径的长度为 O(log(n)) ，所以查询一次的复杂度为O(log(n)) ,而路径压缩之后整棵树又变成左下角的结构，如果再一次和一个绿点合并之后再查询红点，复杂度还是O(log(n)) 的，这就导致产生一个循环，用这样的合并和查询就可能导致不按秩合并的并查集的复杂度降到O(nlog(n)) 。
并查集是我们解决题目过程中常用的数据结构，通常用来解决连通性判定问题。最后给出带按秩合并的并查集的完整模板。
（1）初始化
把每个点所在集合初始化为其自身。通常来说，这个步骤在每次使用该数据结构时只需要执行一次，时间复杂度均为O(N)。
（2）查找
查找元素所在的集合，即根节点。对于判断两个元素是否属于同一个集合，它也是非常有用的。
（3）合并
将两个元素所在的集合合并为一个集合。通常来说，合并之前，应先判断两个元素是否属于同一集合，这可用上面的“查找”操作实现。
（4）时间复杂度
通过按秩合并和路径压缩两个操作，并查集的复杂度可以达到O(Alpha(n)) , 在这里，Alpha(n) 是阿克曼（Ackermann）函数的反函数。这比O(log(n)) 还要快。
不过，这是“均摊复杂度”。也就是说，并不是每一次操作都满足这个复杂度，而是多次操作之后平均每一次操作的复杂度是O(Alpha(n)) 的意思。
例题1：亲戚
实现程序代码：
（1）初始化并查集
for(int i=1;i<=n;i++) f[i]=i; //f[i]存储i的父结点
（2）查找根结点
① 递归代码：
int find(int x) //查找x元素所属集合的根结点
{
if(x!=f[x]) return find(x);
else return x;
}
② 非递归代码：
int find(x)
{
while(x!=f[x]) x=f[x];
return x;
}
（3）合并两个集合
void merge(int x,int y)
{
int r1=find(x); //查找x元素的所在集合的根结点
int r2=find(y); //查找y元素的所在集合的根结点
if(r1!=r2) f[r1]=r2; //将集合r1合并到集合r2上
}
（4）路径压缩代码：
int find(int x) //查找x元素所属集合的根结点
{
if(x!=f[x]) f[x]=find(f[x]);
return f[x];
}
完整代码
#include<bits/stdc++.h>
using namespace std;
int f[5001],n,m,p,x,y;
int find(int i)
{
if(i==f[i]) return i;
else return f[i]=find(f[i]); //路径压缩
}
int main()
{
cin>>n>>m>>p;
for(int i=1;i<=n;i++) f[i]=i; //初始每个点是一个独立的集合，根结点是本身
for(int i=1;i<=m;i++)
{
cin>>x>>y;
int g1=find(x); //查找元素x的根结点
int g2=find(y); //查找元素y的根结点
if(g1!=g2) f[g1]=g2; //合并两个集合
}
for(int i=1;i<=p;i++)
{
cin>>x>>y;
int g1=find(x);
int g2=find(y);
if(g1==g2) cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
return 0;
}
并查集常作为另一种复杂的数据结构或者算法的存储结构。常见的应用有：求无向图的连通分量个数，最近公共祖先（LCA），带限制的作业排序，实现Kruskar算法求最小生成树等。
应用：
1、求无向图连通分量
2、判断两个点是否在一个连通分量里（kruskal）
它在计算机科学中有着广泛的应用，例如，迷宫的生成、确定无向图的连通子图个数、求解最小生成树、亲戚关系的判定、最小公共祖先等等问题，无一例外都用到了并查集。