并查集 ·Disjoint

摘要

并查集(Union-Find Set)用于处理元素间可传递的关系,通常以集合的方式呈现。

并查集本身又是一种树结构(由若干棵树组成的不相交森林),用树的根结点(代表元)来区分不同的集合。


并查集

并查集支持以下基本操作:

  • Get(a) 查询元素 a 所在集合的代表元(根结点).
  • Merge(a,b) 将 a,b 所在的集合合并为一个集合(合并两颗树).

在初始化的时候,每个元素分别属于一个独立集合,集合的代表元即元素本身。

表示元素 i 所在集合的代表元(初始时 ).

int get(int k){if(fa[k]==k)return k;// 如果它本身就是根结点就返回
    return get(fa[k]);// 返回父结点的 fa[]}

显然这是一个递归式查询,复杂度依赖于树的深度。

void merge(int a,int b){if(get(a)==get(b))return;// 如果已经在同一集合,就退出
    fa[get(a)]=get(b);// 把 a 的树根的 fa[] 赋值为 b 的树根 }

简单图解一下
p1.png

判断两元素是否属于同一集合:比较代表元是否相同即可。

简单优化

优化原理:基础的并查集的复杂度依赖于树的深度。

路径压缩

直接图解
p2.png

时间复杂度降为 O(1).

int get(int k){if(fa[k]==k)return k;// 如果它本身就是根结点就返回
    return fa[k]=get(fa[k]);// 路径压缩
}

按秩合并

不太常用,优化思想是,将结点数少的集合合并到结点数大的集合上。

拓展篇

并查集的结构很简单,但能维护的信息也很单一。
只需简单改动原代码,即可维护其他信息

[NOIP2010] 关押罪犯

N 个点,两个集合。有 M 个点对关系, 表示点 u 和点 v 有一个价值为 w 的关系。如果两个点不在同一集合,这个关系就破裂,相当于作废。问如何安排点所在的集合,使得没有破裂的关系的最大价值最小?

我们要尽可能使价值大的关系破裂,因此需要维护 “两个点不在同一集合” 的信息。

并查集只能维护 “两个元素在同一集合” 这一类的信息,却不能维护 “两个元素不在同一集合” 这一类的信息,使用虚点并查集可解决此问题。

我们维护以下两种信息:

  1. friend a b 两个元素属于同一集合
  2. enemy a b 两个元素不属于同一集合

贪心选择冲突大的先处理,直到无法处理就输出

分析

维护的关系的特点在于:

  1. 朋友的朋友是朋友(关系具有传递性
  2. 敌人的敌人不一定是敌人(关系不具有传递性

第一种关系直接使用普通并查集。对于第二种关系,我们将它转化为第一种关系来维护

对于这 个人,我们另外构建 个虚拟的人物,编号为 . 我们定义 的敌人。

因为朋友的敌人是敌人,所以对于关系 enemy a b我们将 合并为朋友,将 合并为朋友.

也就是说,我们直接给每一个人都建立的一个虚拟敌人,并根据第一种关系的传递性,把两个人的敌人关系转化为两个人分别与对方的敌人的朋友关系。

在判断 (a,b) 的关系的时候,我们在并查集中查询 (a,b) 或者 (a,b+n)、(a+n,b) 的关系即可推导出答案。

代码

#include<iostream>
#include<algorithm>
using namespace std;
int n,m,f[40001];

int gf(int k){return f[k]==k?k:f[k]=gf(f[k]);}
void un(int a,int b){f[gf(a)]=gf(b);}

struct data{int p,q,v;};
data e[100001];
bool cmp(data d1,data d2){return d1.v>d2.v;}

int main(){cin>>n>>m;
    for(int i=1;i<=m;i++)cin>>e[i].p>>e[i].q>>e[i].v;
    for(int i=1;i<=n*2;i++)f[i]=i;// 并查集初始化
    sort(e+1,e+m+1,cmp);
    for(int i=1;i<=m;i++){int a=e[i].p,b=e[i].q;// 两个人
        if(gf(a)==gf(b))return cout<<e[i].v,0;// 已经在同一监狱
        else {un(a,b+n);un(b,a+n);}
    }
    cout<<0;
    return 0;
}

[NOI2002] 银河英雄传说

初始时 30000 个点,第 i 个点在第 i 列。维护两种操作:

  1. M i j 把点 i 所在的列作为一个整体拼接到点 j 所在的列的末尾
  2. C i j 问点 i 与点 j 是否在同一列中,如果在同一列输出 i,j 之间的点的个数

并查集有时需要处理边权的问题,维护权值的方法一般与当前结点到代表元的路径有关

比如维护数组 d[i] 表示第 i 个元素到树根的路径长度之类的。

路径压缩的时候注意累加即可。

分析

经典的带权并查集问题

记录每个并查集的代表元(首个点)、大小(点的数量)、到根结点的距离(到第一个点的距离)

每次 Get 和 Merge 的时候顺便更新即可。

注意路径压缩和初始化

#include<bits/stdc++.h>
using namespace std;
const int SZ=30000;

struct disjoint{
    int fa[SZ],d[SZ],s[SZ];//d[] 表示到根结点的距离,s[] 表示该树的大小
    void init(int k){for(int i=1;i<=k;i++)fa[i]=i,d[i]=0,s[i]=1;}
    int gf(int k){
        if(fa[k]==k)return fa[k];
        int res=gf(fa[k]);
        d[k]+=d[fa[k]];// 边权更新
        return fa[k]=res;// 路径压缩
    }
    bool find(int a,int b){return gf(a)==gf(b);}
    void un(int a,int b){//a 在 b 的尾部
        if(find(a,b))return;
        a=gf(a),b=gf(b);
        fa[a]=b,d[a]=s[b],s[b]+=s[a];
    }
};
disjoint d;

int main(){d.init(30000);
    int t;
    scanf("%d",&t);
    while(t--){char opr[5];int i,j;
        scanf("%s%d%d",opr,&i,&j);
        if(opr[0]=='M')d.un(i,j);
        else{if(d.find(i,j)){int ans=d.d[i]-d.d[j];
                printf("%d\n",ans>0?ans-1:0-ans-1);
            }
            else puts("-1");
        }
    }
    return 0;
}

[NOI2015] 程序自动分析

假设 代表程序中出现的变量,给定 个形如 的约束条件,请判定是否可以分别为每一个变量赋予恰当的值,使得上述所有约束条件同时被满足。

要求维护相等与不相等两种关系,显然并查集维护;数字较大就先离散化即可

当然,其实只需要维护相等的关系,最后判断不相等的关系即可

#include<bits/stdc++.h>
using namespace std;
const int N=2e6+6,SIZE=2e6+5;
int t,n,tot,q[N][2],qnt;
struct my_hash_map{struct data{int u,v,nex;};
    data e[SIZE];
    int head[SIZE],cnt;
    int hash(int u){return u%SIZE;}
    int & operator[](int u){int hu=hash(u);
        for(int i=head[hu];i;i=e[i].nex)if(e[i].u==u)return e[i].v;
        e[++cnt]=(data){u,++tot,head[hu]};
        return head[hu]=cnt,e[cnt].v;
    }
    void init(){for(int i=0;i<=cnt;i++)e[i].u=e[i].v=e[i].nex=0;
        memset(head,0,sizeof(head));
        cnt=0;
    }
};
my_hash_map h;
struct disjoint{int f[N];
    void init(int k){for(int i=0;i<=k;i++)f[i]=i;}
    int gf(int k){return f[k]==k?k:f[k]=gf(f[k]);}
    int un(int a,int b){f[gf(a)]=gf(b);}
    int find(int a,int b){return gf(a)==gf(b);}
};
disjoint s;
int main(){scanf("%d",&t);
    while(t--){scanf("%d",&n);
        h.init();
        s.init(n*2);
        tot=qnt=0;
        bool f=true;
        for(int i=1,a,b,c;i<=n;i++){scanf("%d%d%d",&a,&b,&c);
            if(c==1)s.un(h[a],h[b]);
            else ++qnt,q[qnt][0]=h[a],q[qnt][1]=h[b];
        }
        for(int i=1;i<=qnt;i++)
            if(s.find(q[i][0],q[i][1])){f=false;break;}
        if(f)printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}

[POJ1417] True Liars

有一群好人和一群坏人,好人永远说真话,坏人永远说假话。现给出一组话形如 a b yes/no,表示:a 说 b 是好人 / 坏人。问能否唯一确定每个人是好人还是坏人。

对于 yes 的话,易得 a 和 b 是同一类人;对于 no 的话,a 和 b 不是同一类人。那么我们直接维护带权并查集,权值为 1 表示不同类,权值为 0 表示同类。那么这个关系森林的每个集合中又分为两个集合,即好人和坏人。这个可以路径压缩的时侯顺便维护

要求的是唯一确定,那么我们就统计方案数是否为 1 即可。 表示前 i 个集合选 j 个好人的方案数,做一下 DP 即可。最后要输出确切的方案,那么记录一下前缀即可

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
const int N=1e3+5;
int n,p,q;

namespace DIS{int f[N],r[N];
    void init(int k){for(int i=0;i<=k;i++)f[i]=i,r[i]=0;
    }
    int gf(int u){if(f[u]==u)return u;
        int root=gf(f[u]);
        r[u]=r[u]^r[f[u]];
        return f[u]=root;
    }
    void un(int u,int v,int k){int gu=gf(u), gv=gf(v);
        f[gu]=gv, r[gu]=r[u]^r[v]^k;
    }
    bool find(int u,int v){return gf(u)==gf(v);}
}

int f[N][N],pre[N][N];//f[i,j]: 前 i 组选 j 人的方案数
bool go(){scanf("%d%d%d",&n, &p, &q);
    if(n==0&&p==0&&q==0)return 0;
    DIS::init(p+q);
    for(int i=1;i<=n;i++){
        int x,y;
        char op[5];
        scanf("%d%d%s",&x,&y,op);
        if(op[0]=='y')DIS::un(x,y,0);
        else DIS::un(x,y,1);
    }

    int a[N][2]={0};// 以 i 为根的集合的好人与坏人个数
    int b[N][2],lb=0;
    int c[N];// 表示根结点 i 在 b 数组中的下标
    vector<int> man[N][2];
    for(int i=1;i<=p+q;i++)a[DIS::gf(i)][DIS::r[i]]++;
    for(int i=1;i<=p+q;i++)if(a[i][0]) 
        c[i]=++lb, b[lb][0]=a[i][0], b[lb][1]=a[i][1];
    for(int i=1;i<=lb;i++)
        man[i][0].clear(), man[i][1].clear();
    for(int i=1;i<=p+q;i++)man[c[DIS::gf(i)]][DIS::r[i]].push_back(i);
    //for(int i=1;i<=lb;i++)printf("(%d,%d)\n",b[i][0],b[i][1]);

    f[0][0]=1;
    for(int i=1;i<=lb;i++){for(int j=0;j<=p;j++){f[i][j]=pre[i][j]=0;
            if(j>=b[i][0] && f[i-1][j-b[i][0]])
                f[i][j]+=f[i-1][j-b[i][0]], pre[i][j]=j-b[i][0];
            if(j>=b[i][1] && f[i-1][j-b[i][1]])
                f[i][j]+=f[i-1][j-b[i][1]], pre[i][j]=j-b[i][1];
            //printf("f[%d,%d]:%d\n",i,j,f[i][j]);
            //printf("pre[%d,%d]:%d\n",i,j,pre[i][j]);
        }
    }

    if(f[lb][p]!=1)return puts("no"),1;

    vector<int> ans;
    ans.clear();
    int u=p,k=lb;
    while(k!=0){int cur=pre[k][u],cnt=u-cur;
        if(cnt==b[k][0])
            ans.insert(ans.end(), man[k][0].begin(), man[k][0].end());
        else 
            ans.insert(ans.end(), man[k][1].begin(), man[k][1].end());
        --k,u=cur;
    }
    sort(ans.begin(),ans.end());
    for(int i=0;i<ans.size();i++)printf("%d\n",ans[i]);
    puts("end");
    return 1;
}
int main(){while(go());
    return 0;
}
/*
 * BUG#1: 并查集初始化错了,n 改成 p+q
 * BUG#2: 并查集路径压缩的权值合并代码写错
 * BUG#3: 没有考虑好人人数为 0 的情况
 */

[POJ2912] Rochambeau

N 个人玩猜拳,除了一个比较聪明的人以外,其他人只会出单一的一种,给出 m 次猜拳的结果,要求找出那个比较聪明的小伙伴序号,并且输出在第几次猜拳后就可以确定。(注意 <,>,= 前后可能有空格)

可以用拆点并查集或者带权并查集维护猜拳游戏。我们枚举聪明的人,然后不考虑这个人的猜拳游戏,对剩下的游戏判断是否矛盾。如果矛盾说明这个人不是聪明的人,这时要记录出现矛盾的猜拳结果编号。

最后判断是否只有一个人没有矛盾,如果是,那么就输出所有矛盾中最大的那个编号。因为只有把其他人全部否决才能确定这个人是聪明的人。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=505, M=2e3+5;
int n,m;

struct data{
    int a,b,c;//b 表示偏移量
    void read(){
        char x;
        scanf("%d%c%d",&a,&x,&c);
        if(x=='=')b=0;
        else if(x=='<')b=1;
        else b=2;
    }
};
data d[M];

namespace DIS{int f[N*3];
    void init(int k){for(int i=0;i<=k;i++)f[i]=i;}
    int gf(int k){return f[k]==k?k:f[k]=gf(f[k]);}
    void un(int u,int v){f[gf(u)]=gf(v);}
    bool find(int u,int v){return gf(u)==gf(v);}
}
bool go(){if(!~scanf("%d%d",&n,&m))return 0;
    for(int i=1;i<=m;i++)d[i].read();
    int err[N]={0};
    for(int i=0;i<n;i++){//i 是 judge
        DIS::init(n*3);
        for(int j=1;j<=m;j++){int u=d[j].a, v=d[j].c, w=d[j].b;
            if(u==i||v==i)continue;
            DIS::un(u,v+w*n);
            DIS::un(u+n,v+((w+1)%3)*n);
            DIS::un(u+n+n,v+((w+2)%3)*n);
            if(DIS::find(u,u+n)||DIS::find(v,v+n)){err[i]=j;// 出现矛盾
                break;
            }
        }
    }
    int tot=0,ans=0,mx=0;
    for(int i=0;i<n;i++){if(err[i])mx=max(mx,err[i]);
        else ++tot,ans=i;
    }
    if(tot>1)puts("Can not determine");
    else if(tot<1)puts("Impossible");
    else printf("Player %d can be determined to be the judge"
            "after %d lines\n",ans,mx);
    return 1;
}
int main(){while(go());
    return 0;
}

  转载请注明: Sshwy's Blog 并查集 ·Disjoint

 上一篇
贪心小结 贪心小结
小 TAG观察(贪心思路) 猜测(减少决策数量) 证明(从最优解转化为贪心解,并且不改变最优性质,从而证明) 多个贪心组合 贪心与非线性算法 贪心的单调性 贪心性质 贪心算法是一种形式及其多样的算法。它的应用方式很广,简单的简单,难的难。
2018.12.19
下一篇 
Splay 初步 Splay 初步
2019.6.19 编入精选文章。 前言 平衡树是计算机科学中的一类改进的二叉查找树。一般的二叉查找树的查询复杂度是跟目标结点到树根的距离(即深度)有关,因此当结点的深度普遍较大时,查询的均摊复杂度会上升,为了更高效的查询,平衡树应运而生了
2018.12.19
  目录