最重要的数据结构——并查集

我们今天来讲一个大部分竞赛生都最喜欢的一个数据结构——并查集

我们先从一道题入手：亲戚

这时并查集最经典的例题(注意！没有之一！)

我们来看一下这道题，大佬们肯定第一思路就是传递闭包(但是我认为没有没学过并查集的大佬)

我们仔细看看，人数小于等于5000呢！(刚好5000的话Floyd传递闭包大约需要21分钟才能跑出来(ˉ▽ˉ；)...)

这时，我们不得不用并查集了！

先定义一个father数组(用来存某个节点的祖宗)

#include
#define MAX 5010
using namespace std;
int father[MAX];
int main(){

    return 0;
}

其实两个人是否是亲戚，其实就是判断他们的祖先是否是一个人，

那么我们必须写一个判断是否是祖先的代码，如果我们用while循环的话其实不是很好操作(实际上我也没有试过)

大佬们肯定第一个想到的就是递归，我们怎们结束这个递归呢？这是一个十分让新手头痛的问题。

其实十分简单，如果它自己的父亲都是自己的话，那么他肯定是这棵树的祖宗了，其实他是自己的父亲就表示他是这棵树的祖宗了qwq

如果上面的假设条件不成立的话，我们只需要继续找它父亲的父亲是谁这一直递归就行了

所以呢我们就可以写出找x的祖宗的代码：

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

当然，如果你是大佬，看到上面的代码肯定非常不爽(* ￣︿￣)，心里想：不都是一排代码搞定吗？这个作者真是的！(那么你喜欢的代码来了!)

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

我们接下来看并查集的初始化：(这个用不着讲)

for(int i = 1 ; i <= n ; i++) father[i] = i;

其他的就很简单了，接下来看我的AC代码！

#include
#define MAX 5010
using namespace std;
int father[MAX], x, y, n, m, p;
int find(int x){return father[x] == x ? x : find(father[x]);}
int main(){
    scanf("%d%d%d", &n, &m, &p);
    for(int i = 1 ; i <= n ; i++) father[i] = i;
    for(int i = 1 ; i <= m ; i++){
        scanf("%d%d", &x, &y);
        father[x] = find(x);
        father[y] = find(y);
        if(father[x] != father[y]) father[father[x]] = father[father[y]];
    }
    for(int i = 1 ; i <= p ; i++){
        scanf("%d%d", &x, &y);
        if(find(x) == find(y)) cout<<"Yesn";
        else cout<<"Non";
    }
    return 0;
}

今天的并查集就讲到这里了，希望你们有所收获！