浅谈——并查集

· · 个人记录

什么是并查集

  1. 一种树形数据结构
  2. 用来处理集合，元素之间的关系，有两种操作：
    • 查询(小蝌蚪找妈妈爸爸）
    • 合并(小蝌蚪认妈妈爸爸)

什么时候用并查集

  1. 引例P1551 亲戚

这道题看到的第一反应——暴力，但是暴力是肯定会挂掉的(这是显然的~）那么怎么办呢？我们可以想一想，平时振兴广播通知时，总会说：“各班班长来主席台南边开一下会~”而不是"参加……比赛的同学全过来开一下会~"由此我们就可以想到做法了：找到每个队伍的类似于老祖宗的东西，理解成班长也行，只针对这个老祖宗操作就可以了~ 于是就有了并查集这个东西。

2.做法：分三个：初始化，合并，查询.

-初始化:不能没有爹，但又不知道你爹是谁，就只能自己认自己当爹了。

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

查询：这里用到了递归的思想,先找到爹，再让他爹当儿子，去找你爷爷,直到发现他爹就是他自己为止(即达到老祖宗)

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

合并：分别找爹，如果爹相同，就跳过，否则合并。

void work(int x,int y){
    int xx=find(x);//find之前讲过了
    int yy=find(y);
    if(xx==yy) return;
    fa[xx]=yy;
}

把这三个函数怼一起，瞎写个主函数，就完了.

3.让我们在倒流回最初的问题:什么时候用并查集？ 1.出现元素与元素间从属关系时。 2.元素的数量有一坨时。 你可以考虑并查集。

路径压缩

1.首先讲一个故事（强行故事）：在OI界（一个大佬叫做xf），有两个徒弟，一个叫jl,一个叫jh。jh,jl也有徒弟。但因为jl太菜了,所以只收了一个徒弟。而jh则有+oo个，每个徒弟也有+oo个徒弟……。显然，如果我们问一个人他的祖师爷是谁时，如果他是jh门下的，那么他找祖师爷就很麻烦，这时jh为了市场宣传,干脆亲自教所有人。于是几乎所有人都不假思索的说jh是他的祖师爷。因此，一个并查集的著名优化——路径压缩就诞生了，一个OI名师jh也就诞生了……

2.形象理解

3.代码（也就find改了一下）

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

按秩合并

1.思考一个问题：有三棵树第一棵高度为1，第二棵高度为3，第三棵高度为2。一颗一颗地合并，你会把第几棵合并到第几棵上尼？让我们不妨分类讨论一下：

安置合并就是这样，每次我们都把小树合并到大树上，来尽量避免深度的增加。

T103327 冷战

并查集补集

  1. 什么时候用补集

    • 当多个元素之间存在多种(有限)关系的时候

  2. 如何实现

    • 这很难说
    • 拿题说吧 P2024食物链

    这道题一看就发现是得用并查集的因为算法标签上写了它存在集合之间的关系，但又有多组，怎么办呢？这时就要并查集补集了。 开一个三重的并查集(因为有三组关系) 一个表示吃它的，一个表示被吃它的。 建好后如果有一句话的关系违背已有关系，就是假话，ans++； 这样基本上就把这道题切了。

#include<bits/stdc++.h>
using namespace std;
const int maxn=50005;
int n,k,a,b,c,ans;
int fa[maxn*3];
int find(int x){
    if(fa[x]!=x) fa[x]=find(fa[x]);
    return fa[x]; 
}
void work(int a,int b){
    int x=find(a);
    int y=find(b);
    if(x!=y) fa[y]=x;
    return;
}
int main() {
    scanf("%d%d",&n,&k);
    for(int i=1;i<=3*n;i++) fa[i]=i;
    for(int i=1;i<=k;i++) {
        scanf("%d%d%d",&a,&b,&c);
        if(b>n||c>n) {
            ans++;
            continue;
        }
        //a+n a吃的 a+2*n 吃a的 
        if(a==1){
            if(find(b+n)==find(c)||find(b+2*n)==find(c)){
                ans++;
                continue;
            }
            work(b,c);
            work(b+n,c+n);
            work(b+2*n,c+2*n);
        }
        else if(a==2){
            if(find(b+2*n)==find(c)||find(b)==find(c)){
                ans++;
                continue;
            }
            work(b+n,c);
            work(b+2*n,c+n);
            work(b,c+2*n);
        }
    }
    printf("%d",ans);
    return 0;
}

练习 P1525 关押罪犯

带权并查集

练习

P1196 [NOI2002]银河英雄传说

P2342 叠积木