【算法】并查集 — Nt_Yester

正文

并查集你可以理解为是族谱森林（一开始每个节点初始化为自己），我们用 $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

如有不准确请纠正。