因为下一篇要讲克鲁斯卡尔求最小生成树，作为其前置知识的并查集只能被踢出来专门讲一下了嘻嘻。
那么，什么是并查集，请看题面
image.png
所谓并查集，就是对集合进行合并操作并且可以判断某两个元素是否在同一个集合内
那么我们才能维护他？先来介绍数组pre，pre数组代表他的祖先是谁，一个元素自然和他的祖先在同一个集合中，比如现在有0 1 2 3 4 5这6个元素，先合并0 1，在合并2 1，合并完毕之后就是下图的结构，pre[0]=0,pre[1]=0,pre[2]=1,pre[3]=2,其实就是指向上一个节点（你可以把这玩意看成树）
image.png
_我们还是结合代码来理解（以上面这题为例）
//find函数，先去看主函数再来看这个
int find (int x)
{
int r=x;
if(r!=pre[r])//如果他不是树的最高点，那么就接着朝上找
{
r=find(pre[r]);//递归向上找
}
return r;//找到了最高的那个祖宗，返回这个点
}
int main()
{
int n,m;scanf("%d %d",&n,&m);//有n个元素，要进行m次操作（可能是合并，也可能是查询）
int z,x,y;
for(int i=1;i<n+1;i++){
pre[i]=i;//并查集的基本数组，这里是初始化，初始化自己的祖先当然是自己
}
for(int i=1;i<m+1;i++){
scanf("%d %d %d",&z,&x,&y);
if(z==1)
pre[find(x)]=find(y);//如果是合并操作，分别找到两个集合的祖先（由于树的性质，集合的祖先是确定唯一的），然后将其中一个pre修改，完成合并！相当于把森林转换为树
if(z==2)
{
if(find(x)==find(y))//如果不是合并操作，首先判断他们的祖先是不是一个，如果是一个，说明他们在同一个树下（在同一个集合）
printf("Y\n");
else
printf("N\n");//不在就该输出啥输出啥
}
}
return 0;
}
image.png
要一点点从5找上去！！！不太行，所以我们要进行路径压缩，我们在递归的同时更改pre的值，使其变成
image.png
其实只要修改一下find函数
int find (int x)
{
int r=x;
if(r!=pre[r])
{
r=find(pre[r]);
}
pre[x]=r;
return r;//把祖宗的点直接赋给当前节点的pre不就好了吗嘻嘻，这样这个树就不会这么高了，路径就被压缩掉了
}
如果还没有理解可以根据代码手画一下下面的这组数据的图（树），
image.png
好了，毕竟只是前置知识简单介绍一下，方便大家看下一篇的克鲁斯卡尔（并查集的其他优化和带权并查集的出场会很晚的）
