欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

并查集_模版

程序员文章站 2022-04-09 20:10:52
并查集 并查集,在一些有N个元素的集合应用问题中,我们通常是在开始时让每个元素构成一个单元素的集合,然后按一定顺序将属于同一组的元素所在的集合合并,其间要反复查找一个元素在哪个集合中。这一类问题近几年来反复出现在信息学的国际国内赛题中,其特点是看似并不复杂,但数据量极大,若用正常的数据结构来描述的话 ......

并查集

  并查集,在一些有N个元素的集合应用问题中,我们通常是在开始时让每个元素构成一个单元素的集合,然后按一定顺序将属于同一组的元素所在的集合合并,其间要反复查找一个元素在哪个集合中。这一类问题近几年来反复出现在信息学的国际国内赛题中,其特点是看似并不复杂,但数据量极大,若用正常的数据结构来描述的话,往往在空间上过大,计算机无法承受;即使在空间上勉强通过,运行的时间复杂度也极高,根本就不可能在比赛规定的运行时间(1~3秒)内计算出试题需要的结果,只能用并查集来描述。

  并查集是一种树型的数据结构,用于处理一些不相交集合的合并及查询问题。常常在使用中以森林来表示。

例题:

输入格式:

第一行包含两个整数N、M,表示共有N个元素和M个操作。
接下来M行,每行包含三个整数Zi、Xi、Yi
当Zi=1时,将Xi与Yi所在的集合合并
当Zi=2时,输出Xi与Yi是否在同一集合内,是的话输出Y;否则话输出N

输出格式:

如上,对于每一个Zi=2的操作,都有一行输出,每行包含一个大写字母,为Y或者N

模版代码:

#include<cstdio>
#include<iostream>
using namespace std;
int a1,a2,a3,f[200001],n,m;

int getf(int o) {
    if (f[o]==o) return o;
    else return f[o]=getf(f[o]);
}

void make(int v, int u) {
    int t1,t2;
    t1=getf(v);
    t2=getf(u);
    if (t1!=t2) f[t2]=t1;
    return; 
}
void find(int v,int u) {
    int t1,t2;
    t1=getf(v);
    t2=getf(u);
    if (t1==t2) printf("Y\n");
    else printf("N\n");
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i=1; i<=n; i++) f[i]=i;
    for (int i=1; i<=m; i++) {
        scanf("%d%d%d", &a1, &a2, &a3);
        if (a1==1) make(a2, a3);
        else find(a2, a3);
    }
    return 0;
}

主要题目类型:
1.团伙问题(搭桥问题,修路问题):求连通块
2.最小生成树(kruskal)
3.L最近公共祖先(LCA)中的Tarjan
并查集的合并过程:(路径压缩)

int  find(int x) {
    if(fa[x]!=x)  fa[x]=find(fa[x]);
    return fa[x]; 
     //或  return x==fa[x] ? x : fa[x]=find(fa[x]); 
}

因此,并查集在查询是否在同一集合时十分快捷

if(fa[a]==fa[b]) {
    ...
}

与并查集相对的,可以有一种拆分集:

例题:

题目描述:
维护一个数据结构支持下列两个操作:
-删除某条边,表示为”D x”,即为删除第x条边
-查询两点是否属于一个集合,表示为”Q a b”,即为查询节点a与节点b是否在一个集合内,若在同一个集合内,输出”Yes”,否则输出”No”(输出不包括引号)

输入:
第一行包括三个正整数数据结构中节点的个数n,边数m,操作数q
接下来的m行每行包括两个正整数u,v,表示节点u与节点v在同一个集合里
再接下来的q行每行包括一个格式如题描述操作
输出:
对于每一个查询,输出包括一行,表示查询结果,即如果两点属于同一个集合输出”Yes”,否则输出”No”。

实际上,将删除操作存下来,反向就可以建立并查集,将答案倒序输出即可

代码:

#include<cstdio>
#include<cstring>
#include<iostream>
#define CL(X,N) memset(X, N, sizeof(X))
#define LL long long
using namespace std;
const int maxn=1e5+10;
int n, m, q;
int a[maxn], b[maxn];
int u[maxn], v[maxn], f[maxn];
char op[maxn];
bool del_state[maxn];

int _find(int x) {
    return x==f[x] ? x : f[x]=_find(f[x]);
}

void merge(int x, int y) {
    f[_find(y)]=_find(x);
    return ;
}

int main() {
    scanf("%d%d%d", &n, &m, &q);
    for(int i=1; i<=n; i++) f[i]=i;
    for(int i=1; i<=m; i++) scanf("%d%d", a+i, b+i);
    for(int i=1; i<=q; i++) {
        char cmd[2];
        scanf("%s", cmd);
        op[i]=cmd[0];/*存操作符*/ 
        switch(cmd[0]) {
            case 'D' : {
                scanf("%d", u+i);
                del_state[u[i]]=1;/*是否删除*/
                break;
            }
            case 'Q' : {
                scanf("%d%d", u+i, v+i);
                break;
            }
            default : break;
        }
    }
    for(int i=1; i<=m; i++) if(!del_state[i]) merge(a[i], b[i]);
    /*将没被删除的边加入集合*/
    int ans[maxn], cnt=0;
    for(int i=q; i>0; i--) {
        if(op[i]=='Q') {
            if(_find(u[i])==_find(v[i])) ans[cnt++]=1;
            else ans[cnt++]=0;/*正向存答案*/
        }
        else merge(a[u[i]], b[u[i]]);
    }
    for(int i=cnt-1; i>=0; i--) printf(ans[i] ? "Yes\n" : "No\n");/*倒序输出答案*/
    return 0;
}

如果有多种归属的情况,可以考虑建立多倍并查集

例题:

洛谷上 Sooke (dalao)的讲解很详细,此处就不再多说(才不是我懒得写了)这道题比较巧妙的地方在于判断相关性,建议一做。

至于Tarjan,这个算法主要还是于LCA有关,并查集只是中途用来判断两点是否是同一棵子树,不过对并查集的利用还是很巧妙的

下面给出部分Tarjan的模版代码:

void work(int fa,int son) {    //这里是Tarjan部分
    f[son]=son;
    for(int i=head[son];i;i=edge[i].net) {
        int to=edge[i].to;
        if(to==fa) continue;
        dis[to]=dis[son]+edge[i].c;    /*更新深度*/
        work(son,to);
        f[to]=son;
    }
    ...
return ; }

由于递归过程中,work(son, to) 比 f[to]=son先执行,因此可以看做这是在树上自底向上将节点加入并查集

". . ." 部分可以是对深度或距离的更新查询,但由于查询顺序不一定于答案顺序相同(work(fa, son) 函数像先序遍历),
就需要先存再输出,不过整个算法的时间复杂度是十分优秀的(因为只查询了一遍)

对于答案顺序的具体原因这里不做更多说明,希望了解的还请浏览其他博客

(最后好像水了点)