一、并查集

1.定义

首先，并查集是个啥？

我们可以用一个更通俗一些的例子来理解：

有a，b，c三个人，

b是a的上司，a又是c的上司，但是c却不认识b，这显然是不合理的，所以我们要让b变成最大的上司。

首先我们定义一个f数组来维护这段关系，f[a]=b表示a的上司是b，f[c]=a表示c的上司是a，那如何将c的最大上司变成b呢？

定义一个find函数

//初始化每个人的上司是自己，即令f[i]=i
int find(x){
    if(f[x]==x) return x;
    return find(f[x]);//递归找到自己最大的上司
}
f[c]=find(f[a]);//令b变为c的上司

这样我们就解决了这个问题

2.路径压缩

如果b有上司，b的上司也有上司，上司的上司还有上司...

可以发现如果这段关系有很多层，那么我们需要递归很多次才能找到c的最大上司x，时间复杂度可能会很高，所以我们可以用路径压缩优化

我们将c到x中间的那些节点删去，直接令f[c]等于c的最大上司x，这样便能够大大提高效率

代码如下：

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

二、例题

1.洛谷P3367 【模板】并查集

https://www.luogu.org/problem/P3367

题目描述

如题，现在有一个并查集，你需要完成合并和查询操作。

输入格式

第一行包含两个整数N、M，表示共有N个元素和M个操作。

接下来M行，每行包含三个整数Zi、Xi、Yi

当Zi=1时，将Xi与Yi所在的集合合并

当Zi=2时，输出Xi与Yi是否在同一集合内，是的话输出Y；否则话输出N

输出格式

如上，对于每一个Zi=2的操作，都有一行输出，每行包含一个大写字母，为Y或者N

输入输出样例

输入 #1

输出 #1

N
Y
N
Y

说明/提示

时空限制：1000ms,128M

数据规模：

对于30%的数据，N<=10，M<=20；

对于70%的数据，N<=100，M<=1000；

对于100%的数据，N<=10000，M<=200000。

模板题，直接上代码

#include<bits/stdc++.h>
using namespace std;
int f[100001],n,m,a,b,c;
int find(int x){//并查集函数
    if(f[x]==x) return x;
    return f[x]=find(f[x]);
}
int main(void){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) f[i]=i;//初始化，自己是自己的上司
    for(int i=1;i<=m;i++){
        scanf("%d%d%d",&a,&b,&c);
        if(a==1) f[find(b)]=find(c);//合并，令c的上司成为b的上司的上司
        else{
            if(find(b)==find(c)) cout<<"Y"<<endl;//判断两人的上司是否为同一个人并输出
            else cout<<"N"<<endl;
        }
    }
    return 0;
}

持续更新ing...

上司

并查集详解