最基本的并查集：维护n个元素间的相关关系
并查集的初始化为将n个元素各自看成一个集合，并通过不断的合并命令（将两个集合的根节点指向同一处）和查找命令（查找两个集合的根节点是否相同）来实现n个元素间相关关系的维护。通常使用多个树形结构即森林来表示各个集合，在初始化时将n个树的根节点指向自身，并在后续查找和合并的过程中不断维护
借用《啊哈算法》中的比喻形象解释，可以看做有n个小偷属于不同（也可能相同）的团伙，为了确定两个小偷是否属于同一个团伙，最方便的方式是查找他们的上级是否相同。
例如有5个小偷 1 2 3 4 5，那么设置数组fa[n+5],并依次初始化为自己的下标（用于标记自己的上级，如初始状态下fa[1]=1说明1此时上级是1本身)。
已知3和5是同一个团伙，那么设3为5的上级（反之亦成立），此时fa[5]=3。此操作称为合并操作（union）
又有已知4和5为同伙，那么只需要令fa[4]=5，即4的上级为5（反之亦然）。
此时我们查询 1 和 4是否为同一个团伙，只需要查找1 和 4 的大BOSS是不是同一个人。发现1的上级为1本身，而4的上级为5，5的上级为3，因此4的上级为3，发现二者上级不同，说明不是同一个团伙。该过程中对上面两个元素查找上级的操作称为查找操作(find)
优化_对find操作的优化
由图3可看出,当我们合并时有可能使得这棵树过长而影响效率,因此可以使用名为路径压缩的方式优化查找过程,即在查找过程中,如果自己的父节点不是根节点,则将自己和自己父节点同时指向根节点.仍然引用《啊哈算法》的比喻，当你的上级归顺于他的上级时，他的上级也就想当然变成了你的上级。该过程便被称为路径压缩。
/*
前置定义：定义一个int fa[]用于储存每个元素的根节点
这是使用路径优化后的查找 find函数
*/
int find(int x){
if(fa[x]!=x)
fa[x]=find(fa[x]);
return fa[x];
}
优化_对union 操作的优化
既然可以通过对查找过程优化来进行路径压缩，那么有没有什么方式可以对合并的方式进行优化呢？答案是肯定的。
首先对合并的过程进行分析可知：
至此我们可以处理并查集的一些模板题，例如洛谷P3367 【模板】并查集
ac代码如下：
#include<stdio.h>
int* fa;
int find(int x){
if(fa[x]!=x)
fa[x]=find(fa[x]);
return fa[x];
}
void union_it(int x,int y){
int fx=find(x);
int fy=find(y);
if(fx!=fy)
fa[fx]=fy;
}
int main(){
int n,m;
scanf("%d %d",&n,&m);
fa=(int*)malloc((n+5)*sizeof(int));
for(int i=0;i<n;i++)
fa[i]=i;
for(;m--;){
int c,x,y;
scanf("%d %d %d",&c,&x,&y);
if(c==1)
union_it(x,y);
else{
if(find(x)==find(y))
printf("Y\n");
else
printf("N\n");
}
}
return 0;
}