并查集

高级数据结构中的初级数据结构。 （手动滑稽）

是一种可以动态维护若干个不重叠的集合，并支持合并与查询操作的数据结构。

其本质是维护一个森林，均摊复杂度 \(O(\sqrt n)\)，效率很高的。

基础操作

初始化

就是将自己的祖先指向自己，后面有用。

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

合并

这么简单的操作为什么要单拿出来讲

其实很简单，就是合并两者的祖先，讲一个祖先指向另一个（相当于称为另一个的子节点）

Merge(int x,int y){
    fa[find(x)]=find(y);
}

查询

就是利用 \(find()\) 函数进行查找，看两者的祖先是否相同。

最简单的 \(find()\) 函数写法如下：

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

当然如果仅仅是这样的话时间复杂度是 \(O(n)\) 的，还不如不用，所以有一个神奇的优化——路径压缩。

基本上没改什么 ??

int find(int x){
    if(x==fa[x]) return x;
    return fa[x]=find(fa[x]);//重点
}

还有一个优化叫按轶合并，可以进一步优化，但一般考试的时候路径压缩就够用了。

实践

假设要你实现一个能执行两种操作的代码：

1. \(M\) 操作：合并两个数所在的集合。
2. \(A\) 操作：询问两个数是够在同一个集合中。

简单的代码如下：

scanf("%d %d",&a,&b);
'M':
    Merge(a,b);
'A':
    if(find(a)==find(b)) printf("YES\n");
    else printf("NO\n");

基础例题

程序自动分析

程序自动分析

并查集经常用于维护具有传递关系的东东

这道题的思路就是：并查集+离散化

太简单了直接上代码吧 ヾ(?°?°?)??

#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#define N 1000010
using namespace std;

int T,n,a[N*2],b[N*2],fa[2*N];
bool flag[N];

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

void Merge(int x,int y){
    fa[find(x)]=find(y);
    return;
}

int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        for(int i=1;i<=n;i++){
            scanf("%d %d",&a[2*i-1],&a[2*i]);
            scanf("%d",&flag[i]);
            b[2*i-1]=a[2*i-1];
            b[2*i]=a[2*i];
        }
        sort(b+1,b+2*n+1);
        int m=unique(b+1,b+2*n+1)-(b+1);
        for(int i=1;i<=2*n;i++) fa[i]=i;
        for(int i=1;i<=n;i++){
            if(flag[i]==0) continue;
            int fx=lower_bound(b+1,b+m+1,a[2*i-1])-b;
            int fy=lower_bound(b+1,b+m+1,a[2*i])-b;
            Merge(fx,fy);
        }
        bool fff=true;
        for(int i=1;i<=n;i++){
            if(flag[i]==1) continue;
            int fx=lower_bound(b+1,b+m+1,a[2*i-1])-b;
            int fy=lower_bound(b+1,b+m+1,a[2*i])-b;
            if(find(fx)==find(fy)){
                printf("NO\n");
                fff=false;
                break;
            }
        }
        if(fff) printf("YES\n");
    }
    return 0;
}

Supermarket

超市

这道题我用了两种做法做，这里仅介绍 “贪心+并查集” 方法。（还有一种是贪心+小根堆）

首先肯定是尽量买价值大的东东，所以就按照价值排个序。

然后就有并查集的玄学操作了：

1. 找到商品 \(i\) 的祖先 \(find(i)\)。
2. 倘若 \(find(i)!=0\) ，加上 \(i\) 的价值，合并 \(find(i)\) 与 \(find(i)-1\)。
3. 否则跳过。

其实这里的并查集维护的是 \(i\) 能插入的最晚时间。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
#include<algorithm>
#define N 10010
using namespace std;

int n,fa[N];
struct node{
    int p,d;
}a[N];

bool cmp(node a,node b){
    return a.p>b.p;
}

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

void Merge(int x,int y){
    fa[find(x)]=find(y);
    return;
}

int main(){
    while(~scanf("%d",&n)){
        int t=0;
        for(int i=1;i<=n;i++){
            scanf("%d %d",&a[i].p,&a[i].d);
            t=max(t,a[i].d);
        }
        for(int i=0;i<=t;i++) fa[i]=i;
        sort(a+1,a+n+1,cmp);
        int ans=0;
        for(int i=1;i<=n;i++){
            int fx=find(a[i].d);
            if(!fx) continue;
            ans+=a[i].p;
            fa[fx]=fx-1;
        }
        printf("%d\n",ans);
    }
    return 0;
}

“边带权” 与 “扩展域” 并查集

边带权

有边权就可以维护更多的东西。是不是很高级

[NOI2002]银河英雄传说

很简单的边带权并查集。

对于每个点，分别记录所属链的头结点、该点到头结点的距离以及它所在集合的大小。

每次合并将 \(y\) 接在 \(x\) 的尾部，改变 \(y\) 头的权值和所属链的头结点，同时改变 \(x\) 的尾节点。

注意：每次查找的时候也要维护每个节点的权值。

每次查询时计算两点的权值差。

#include<cstdio>
#include<algorithm>
#include<cmath>
#include<iostream>
#include<cstring>
#define N 30010
using namespace std;

int T,fa[N],sum[N],dis[N];

int find(int x){
    if(x==fa[x]) return x;
    int xx=find(fa[x]);
    dis[x]+=dis[fa[x]];
    return fa[x]=xx;
}

int main(){
    scanf("%d",&T);
    for(int i=1;i<=N;i++) fa[i]=i;
    for(int i=1;i<=N;i++) sum[i]=1;
    for(int i=1;i<=N;i++) dis[i]=0;
    
    int x,y;
    char c;
    while(T--){
        cin>>c;
        scanf("%d %d",&x,&y);
        int fx=find(x);
        int fy=find(y);
        if(c=='M'){
            dis[fx]+=sum[fy];
            fa[fx]=fy;
            sum[fy]+=sum[fx];
            sum[fx]=0;
        }
        else{
            if(fx!=fy) printf("-1\n");
            else printf("%d\n",abs(dis[x]-dis[y])-1);
        }
    }
    return 0;
}

扩展域

就是有多个域的并查集。

食物链

并查集能维护连通性、传递性，通俗地说，亲戚的亲戚是亲戚。

然而当我们需要维护一些对立关系，比如 敌人的敌人是朋友 时，正常的并查集就很难满足我们的需求。

常见的做法是将原并查集扩大一倍规模，并划分为两个种类。（即扩展域）

在同个种类的并查集中合并，和原始的并查集没什么区别，仍然表达他们是朋友这个含义。

考虑在不同种类的并查集中合并的意义，其实就表达 他们是敌人 这个含义了。

按照并查集美妙的 传递性，我们就能具体知道某两个元素到底是 敌人 还是 朋友 了。

至于某个元素到底属于两个种类中的哪一个，由于我们不清楚，因此两个种类我们都试试。

容易忽略的是，题目中指出若 \(x\) 吃 \(y\)，\(y\) 吃 \(z\)，应有 \(x\) 被 \(z\) 吃

既然关系满足上述传递性，我们就能放心地使用扩展域并查集来维护啦。

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<cstring>
#define N 50010
using namespace std;

int n,k,fa[3*N],ans=0;

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

int main(){
    scanf("%d %d",&n,&k);
    for(int i=1;i<=3*n;i++) fa[i]=i;
    int flag,x,y;
    for(int i=1;i<=k;i++){
        scanf("%d %d %d",&flag,&x,&y);
        if(x>n || y>n){ans++;continue;}
        if(flag==1){
            if(find(x+n)==find(y) || find(x)==find(y+n)){ans++;continue;}
            fa[find(x)]=find(y);
            fa[find(x+n)]=find(y+n);
            fa[find(x+2*n)]=find(y+2*n);
        }
        else{
            if(x==y || find(x)==find(y) || find(x)==find(y+n)){ans++;continue;}
            fa[find(x+n)]=find(y);
            fa[find(x+2*n)]=find(y+n);
            fa[find(x)]=find(y+2*n);
        }
    }
    printf("%d\n",ans);
    return 0;
}

方法选择

有的题目可以用边带权的并查集，前提是需要维护一些具体数值。

有的可以用扩展域并查集，前提是需要维护一些传递性关系。

那么有没有两种方法都可以用的题目呢？ 答案是肯定的。

[CEOI1999]Parity Game

关于本题主要做法

由于数列中只有0或1，那么使先开一个 \(s\) 数组表示前缀和，那么

\(s[j]?s[i?1]\) 是奇数时，则 \([i..j]\) 区间中的奇数个数为奇数，反之，为偶数。

区间的关系是已知的，\(s\) 是未知的，那么就可以用区间的条件来限定前缀和，如果有矛盾，就可以直接输出。

边带权

这题的传递关系不止一种：

1. 若 \(x_1\) 与 \(x_2\) 奇偶性相同，\(x_2\) 与 \(x_3\) 奇偶性相同，那么 \(x_1\) 与 \(x_3\) 奇偶性相同。这种情况与“程序自动分析“中的等于关系一样。
2. 若 \(x_1\) 与 \(x_2\) 奇偶性相同，\(x_2\) 与 \(x_3\) 奇偶性不同，那么 \(x_1\) 与 \(x_3\) 奇偶性不同。
3. 若 \(x_1\) 与 \(x_2\) 奇偶性不同，\(x_2\) 与 \(x_3\) 奇偶性也不同，那么 \(x_1\)与 \(x_3\) 奇偶性相同。

边权 \(d[x]\) 为\(0\)，表示 \(x\) 与 \(f[x]\) 奇偶性相同；为 \(1\) ，表示 \(x\) 与 \(f[x]\) 奇偶性不同。在路径压缩时，对 \(x\) 到根路径上的所有边权做异或 (\(xor\)) 运算，即可得到 \(x\) 与根的奇偶性关系。

设在离散化后 \(l?1\) 和 \(r\) 的值分别是 \(x\) 和 \(y\)，\(ans\) 表示回答（\(0\) 代表偶数个，\(1\)代表奇数个）。

先判断 \(x\) 与 \(y\) 是否在同一个集合里。然后 \(d[fx] ^ d[fy]\)（\(fx=getfather(x);fy=getfather(y)\)），判断 \(x\) 与 \(y\) 的奇偶性关系。若 \(d[fx] ^ d[fy]!=ans\) ，则判断为小A撒谎。

若 \(x\) 和 \(y\) 不在同一个集合里，则合并两个集合。设两个集合的树根分别为 \(r_1\)和 \(r_2\)。因为路径 \(x\)~\(y\) 由路径 \(x\) ~\(y\)，\(r_1\)-\(r_2\) 与 \(r_2\)~\(y\) 组成，所以 \(ans=d[x]\) \(xor\) \(d[y]\) \(xor\) \(d[r_1]\)。进而推出 \(d[r_1]=d[x]\) \(xor\) \(d[y]\) \(xor\) \(ans\)。

#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#define M 10010
using namespace std;

int n,m,cnt=0,b[2*M],fa[2*M],d[2*M];
struct node{
    int x,y,ans;
}a[M];

int find(int x){
    if(fa[x]==x) return x;
    int root=find(fa[x]);
    d[x]^=d[fa[x]];
    return fa[x]=root;
}

void init(){
    char str[5];
    scanf("%d %d",&n,&m);
    for(int i=1;i<=m;i++){
        scanf("%d %d %s",&a[i].x,&a[i].y,str);
        a[i].ans=(str[0]=='o'?1:0);
        b[++cnt]=a[i].x-1;
        b[++cnt]=a[i].y;
    }
    sort(b+1,b+cnt+1);
    n=unique(b+1,b+cnt+1)-(b+1);
    return;
}

void work(){
    for(int i=1;i<=n;i++) fa[i]=i;
    for(int i=1;i<=m;i++){
        int x=lower_bound(b+1,b+n+1,a[i].x-1)-b;
        int y=lower_bound(b+1,b+n+1,a[i].y)-b;
        int fx=find(x);
        int fy=find(y);
        if(fx==fy){
            if((d[x]^d[y])!=a[i].ans){
                printf("%d\n",i-1);
                return;
            }
        }
        else {
            fa[fx]=fy;d[fx]=d[x]^d[y]^a[i].ans;
        }
    }
    printf("%d\n",m);
    return;
}

int main(){
    init();
    work();
    return 0;
}

扩展域

扩展域，顾名思义，就是将原来并查集扩大，已达到储存每个元素的多个关系。

如本题就要记录与自己相同的和与自己不同的，就将 \(f\) 数组开大到原来的两倍，\(f[i]\) 表示与自己相同的集合，\(f[i+n]\)表示与 \(i\) 不同的元素集合。

#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#define M 10010
using namespace std;

int n,m,cnt=0,b[2*M],fa[2*M];
struct node{
    int x,y,ans;
}a[M];

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

void init(){
    char str[5];
    scanf("%d %d",&n,&m);
    for(int i=1;i<=m;i++){
        scanf("%d %d %s",&a[i].x,&a[i].y,str);
        a[i].ans=(str[0]=='o'?1:0);
        b[++cnt]=a[i].x-1;
        b[++cnt]=a[i].y;
    }
    sort(b+1,b+cnt+1);
    n=unique(b+1,b+cnt+1)-(b+1);
    return;
}

void work(){
    for(int i=1;i<=2*n;i++) fa[i]=i;
    for(int i=1;i<=m;i++){
        int x=lower_bound(b+1,b+n+1,a[i].x-1)-b;
        int y=lower_bound(b+1,b+n+1,a[i].y)-b;
        int x_odd=x,x_even=x+n;
        int y_odd=y,y_even=y+n;
        if(a[i].ans==0){
            if(find(x_odd)==find(y_even)){
                printf("%d\n",i-1);
                return;
            }
            fa[find(x_odd)]=find(y_odd);
            fa[find(x_even)]=find(y_even);
        }
        else{
            if(find(x_odd)==find(y_odd)){
                printf("%d\n",i-1);
                return;
            }
            fa[find(x_odd)]=find(y_even);
            fa[find(x_even)]=find(y_odd);
        }
    }
    printf("%d\n",m);
    return;
}

int main(){
    init();
    work();
    return 0;
}

总结

比较简单而实用的数据结构。ヾ(=?ω?=)o

完结撒花。

并查集

原文：https://www.cnblogs.com/lpf-666/p/12539933.html