简述并查集

并查集是一种树形结构，一般情况下对N个初始独立的元素支持合并（将两个元素所在的集合合并）和查询（查询两个元素是否在一个集合）两种操作

这里借用洛谷的P3367来理解其作用更好
抄一下题面：

理解作用之后来看实现：
我们需要一个数组 fa[] 来储存每个元素的大哥，在初始情况下，每个元素都是独立的一个集合，所以大哥就是自己。如果两个元素的大哥相同，或者大大哥、大大大哥等向上可以追溯到公共的领导，则这两个元素处于一个集合，反之不是

看一个图

如上图所示，x和2拥有共同的大哥1，所以x和2属于一个集合，但是x和345结点虽然没有共同的 大哥 ，但是还有共同的祖先1，这是他们仍属于一个集合（虽然看起来像是废话，但是很重要）。上图中共有两个集合
对于一个节点的祖先查询，可以用递归或者循环解决，思路是如果一个节点的大哥不是自己，就找他的大哥，看他的大哥的祖先是不是自己

int find(int x){//查询x的大哥
     if(fa[x]==x)    return x;    //如果祖先是自己，则他是此集合的树的根节点
     else return find(fa[x]);     //如果不是，向上找一层，看他的父节点
     //else return fa[x]=find(fa[x]);
}

对与合并的操作，需要注意的是合并x，y两个元素时候指的是所在的集合，如上图中合并5和d节点，就会使得所有点归于同一个集合。所以，我们使用擒贼先擒王的思想，合并两个团伙AB，就是让A团伙的大哥加入到B团伙当小弟，这样他的小弟也跟着他归顺B团伙了

void merge(int a,int b){
     //合并ab
     int f1=find(a),f2=find(b);
     fa[f1]=f2;
     //让A团伙的大哥归顺B团伙和反之没有区别，我们只关心两个人是否在一个团伙，不关心上下级关系
 } 

这样以来，就实现了并查集的功能
现在有一个严重的问题，我们的find函数在树中按照一级一级向上的顺序查找，在类线性结构中的表现会及其差劲，如
1-2-3-4-5-6-7-8-9-10-11-12
假设1是根节点，这里有他的12代子孙，则每次find(12)时都需要向上走11层，效率很低而且没有必要，并查集只关心两个元素集合的是/否关系，不关心层级，所以我们一般都会使用路径压缩，如果查到了12等人的大哥是1，就直接让12等变成1的直接下级
用代码实现就是find函数中注释的部分，很简单

最后贴上完整的代码

//P3367【模板】并查集
 include<bits/stdc++.h>
 using namespace std;

 const int MAXN=500000;
 int fa[MAXN];

 inline void init(){ //初始化时每个人都是独立的
     for(int i=0;i<MAXN;i++)
         fa[i]=i;
 }

 int find(int x){
     if(fa[x]==x)    return x;
     else return fa[x]=find(fa[x]);
 }

 int main(){
     init();

     int n,m;
     scanf("%d%d",&n,&m);

     int opt,x,y,f1,f2;
     for(int i=1;i<=m;i++){//这里为了方便没有再写成函数
         scanf("%d%d%d",&opt,&x,&y);
         f1=find(x),f2=find(y);
         if(opt==1)
             fa[f1]=f2;
         else if(f1==f2) puts("Y");
         else puts("N");
     }
     return 0;
 }

并查集是一个十分强大且好用的算法，在关于图的连通性问题上往往可以发挥巨大的作用，一个典型的例子就是Kruscal最小生成树。但是他同时有着只合不分的致命缺点，如果需要拆分则不能考虑用并查集维护