正文

并查集你可以理解为是族谱森林(一开始每个节点初始化为自己),我们用 $f_i$ 表示 $i$ 的父亲,一般有以下操作:并和查。

先来说查,查就是字面意思:查找 $i$ 的最早祖先,我们可以递归查找,查找 $i$ 的父亲,再查找 $i$ 的父亲的父亲,依次递归,就有了以下代码。

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

但是我们发现,如果查找一个人的最早祖先,就需要付出 $O(n)$ 的时间复杂度(虽说比较小但还是不划算),所以我们就需要想另一种方法,然后我们发现,在最早祖先下的所有祖先,好像并没有什么用,所以我们可以用 $f_i$ 表示 $i$ 的最早祖先,这种方法我们称为路径压缩。

int find(int x) {
    if (f[x]==x) {
        return x;
    }
    return f[x]=find(f[x]);//路径压缩
}

再来说并,并就是把两棵族谱树连在一起,怎么连呢?很简单我们只需找到 $i$ 和 $j$ 的最早祖先,然后将其中 $i$ 的最早祖先的祖先即 $f_{find(i)}$,表示为 $j$ 即可(也可以反过来),代码如下。

void join(int x,int y) {
    int nx=find(x),ny=find(y);//i、j 的最早祖先
    f[nx]=ny;//并
}

拓展

我们在做并查集时,$f_i$ 一般表达的是亲戚关系,但在 P1892 中有两种关系,一种为亲戚关系,另一种为敌对关系,这就涉及到了另一个知识:反集。$i$ 的反集一般用 $f_{i+n}$ 来表示,其他的基本与并查集无异(但是在 join(i+n,j)中,两个参数千万不能写反),上代码(P1892):

#include <iostream>

using namespace std;
int n,m,ans;
char c;
int f[2001];

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

void join(int x,int y) {
    int nx=find(x),ny=find(y);
    if (nx!=ny) {
        f[nx]=ny;
    }
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
#endif
    cin>>n>>m;
    for (int i=1;i<=2*n;i++) {
        f[i]=i;
    }
    for (int i=1;i<=m;i++) {
        cin>>c;
        int t1,t2;
        cin>>t1>>t2;
        if (c=='F') {
            join(t1,t2);
        } else if (c=='E') {
            join(t1+n,t2);
            join(t2+n,t1);
        }
    }
    for (int i=1;i<=n;i++) {
        if (f[i]==i) {
            ans++;
        }
    }
    cout<<ans;
}

可以发现基本与并查集无异,只是需要多写一个 join

如有不懂还可参考 there

再来看一道题 P2024 ,第一眼看上去就觉得是一个反集,于是便自信的打了一个反集上去,然后,成功地连样例都没过。

………

为什么?仔细读题你会发现,题目中的关系为:$A$ 吃 $B$,$B$ 吃 $C$,$C$ 吃 $A$,已就是说 $A$ 吃 $B$,$B$ 不吃 $A$,所以反集不成立(因为这是单向关系),所以我们就素要把 $f$ 数组再开一倍(也就是开三倍)去储存关系,即 $f_i$ 表示为 $i$ 的亲戚,$f_{i+n}$ 表示为 $i$ 的猎物,$f_{i+n+n}$ 表示为 $i$ 的天敌,再使用并查集去套即可 AC,上代码:

#include <iostream>
#include <cstdio>

using namespace std;
int f[300005];
int n,k,ans;

inline int read() {//要写快读,cin 过不去
    int sum=0;
    char ch=getchar();
    while(ch>'9'||ch<'0') ch=getchar();
    while(ch>='0'&&ch<='9') sum=sum*10+ch-48,ch=getchar();
    return sum;
}

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

void join(int x,int y) {
    int nx=find(x),ny=find(y);
    f[nx]=ny;
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
#endif
    int x,y,z;
    n=read(),k=read();
    // cin>>n>>k;
    for (int i=1;i<=3*n;++i)  {
        f[i]=i;
    }
    for(int i=1;i<=k;++i) 
    {
        z=read(),x=read(),y=read();
        // cin>>z>>x>>y;
        if (x>n or y>n) {
            ans++;
            continue;
        }
        if(z==1)
        {
            if(find(x+n)==find(y) or find(x+n+n)==find(y)) {
                ans++;
            } else {
                join(x,y);
                join(x+n,y+n);
                join(x+n+n,y+n+n);
            }
        } else if (z==2) {
            if (x==y) {
                ans++;
            } else if (find(x)==find(y) or find(x+2*n)==find(y)) {
                ans++;
            } else {
                join(x,y+n+n);
                join(x+n,y);
                join(x+n+n,y+n);
            }
        }
    }
    printf("%d\n",ans);
    return 0;
}

并查集的扩展应用实际就是开多倍的 $f$ 数组去表达关系,并没有什么难处。

题目

p1551

p1536

p1621

p1892

finally

如有不准确请纠正。

分类: 文章

Evol_Yester_Nt

抽紫烟,吸纯氧,健康生活everyday

0 条评论

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注

*

code