思想

并查集是一种用于管理元素所属集合的数据结构，实现为一个森林，其中每棵树表示一个集合，树中的节点表示对应集合中的元素．

——OI wiki

感觉这个定义还挺好理解的。

思想也很简单，把一个集合抽象成一颗树，此时树根就是这个集合的代表元素。

这种结构支持两种操作：查询与合并。

查询就是寻找所在集合的代表元素，显然，两个代表元素相同的两个元素处于同一个集合。

int find(int x){
    if(f[x]==x)return x;
    else return find(f[x]);//f数组初值是f[x]=x
}

合并就是使两个集合拥有同一个代表元素，最简单的办法就是将一个集合的根节点连接到另一个集合的根节点。

x=find(x),y=find(y);
f[x]=y;

朴素的并查集合并和查询每次都是$O(n)$的，对于$m$次查询就是$O(nm)$的。

‍

这个复杂度显然是不够好的，常用的有两种考虑优化：路径压缩和按秩合并。

‍

路径压缩：可以发现的是，并查集只关注每个集合的代表元素。因此，只要我们在回溯时顺便把树变成一个菊花，就会明显快很多。均摊时间复杂度为$O(log n)$。

int find(int x){
    return x==f[x]?x:f[x]=find(f[x]);
}

按秩合并：这里的秩可以指树的高度或树的节点数，不影响时间复杂度，核心思想都是将小结构合并到大结构里从而减少操作次数。单独使用按秩合并优化也能将均摊时间复杂度优化到$O(log n)$，理论上按节点数合并慢于按高度合并。

‍

（但是因为未知原因加上按秩合并优化今后速度明显变慢，加上一般只需要路径压缩，这里就不贴代码了。）

‍

下面是只有路径压缩的模板题。

‍

P3367 【模板】并查集

#include"algorithm"
#include"iostream"
#include"cstring"
#include"climits"
#include"cstdio"
#include"random"
#include"string"
#include"bitset"
#include"ctime"
#include"queue"
#include"map"
#define ls o<<1
#define rs o<<1|1
#define db double
// #define ll long long
using ll = long long;
// #define int long long

#define  f(i,a,b) for(int i=a;i<=b;i++)
#define ff(i,a,b) for(int i=a;i>=b;i--)

using namespace std;

ll rd()<%ll x=0,w=1;char c=getchar();while(c<'0'||c>'9')<%if(c=='-')w=-1;c=getchar();%>while(c<='9'&&c>='0')<%x=x*10+(c-'0');c=getchar();%>return x*w;%>

mt19937 r(time(0));

namespace Wunsch{

    int n,m;

    int f[200010];

    int find(int x){
        return x==f[x]?x:f[x]=find(f[x]);
    }

    bool main(){
        n=rd();m=rd();
        f(i,1,n){
            f[i]=i;
        }
        while(m--){
            int opt=rd();
            int x=rd();
            int y=rd();
            int fx=find(x);
            int fy=find(y);
            if(opt==1){
                if(fx==fy)continue;
                f[fx]=fy;
            }
            else{
                if(fx==fy){
                    printf("Y\n");
                }
                else{
                    printf("N\n");
                }
            }
        }
        return 1;
    }

}

bool amiya=Wunsch::main();

main(){;}

‍