并查集和其他并查集-平芜编程栈

并查集

这篇讲解并查集及拓展主要放在并查集进阶内容上

经典并查集

并查集用于维护不相交集合的合并与查询共有两个操作:

f i n d ( x ) find(x)find(x)返回x xx所在集合的代表元(根/老大)
m e r g e ( x , y ) merge(x, y)merge(x,y)将x , y x, yx,y所在集合合并

用数组f a [ i ] fa[i]fa[i]表示i ii的父亲节点一个集合的代表元的父亲是它自己
初始化f a [ i ] = i fa[i]=ifa[i]=i

简洁模板如下

intfa[MAXN];intfind(intx){if(fa[x]==x)returnx;// 若父亲为自己 则找到了该集合的代表元returnfa[x]=find(fa[x]);// 路径压缩}voidmerge(intx,inty){fa[find(x)]=find(y);// 将x集合代表元的父亲指向y集合代表元}

find的路径压缩

也就是我们在上面看到的f a [ x ] = f i n d ( f a [ x ] ) fa[x]=find(fa[x])fa[x]=find(fa[x])目的是为了把x xx的父亲自动指向当前集合的代表元最终路径压缩的结果就是:

带权并查集

经典并查集仅能判断两元素是否在同一集合而带权并查集解决了元素之间的相对关系比如:

与根节点的距离
与父节点的差值
等等相对关系

核心思想
每个节点除了f a [ x ] fa[x]fa[x]以外再来一个v a l [ x ] val[x]val[x]表示节点x xx到其父节点f a [ x ] fa[x]fa[x]的某种关系

故在路径压缩时需要将v a l [ x ] val[x]val[x]更新为x xx到根节点的关系
在合并操作中需要计算出两根关系

code
我们以维护节点到根的距离为例设一个d [ x ] d[x]d[x]为x xx到父节点f a [ x ] fa[x]fa[x]的距离
find操作:

intfind(intx){if(fa[x]==x)returnx;introot=find(fa[x]);// 先递归得根// 更新x到根的距离 = x到原父节点距离+父节点到爷爷节点(压缩后即为根节点)的距离d[x]+=d[fa[x]];returnfa[x]=root;//路径压缩

merge操作:

//将x集合同y集合合并 且x到y的距离为wvoidmerge(intx,inty,intw){intrx=find(x),ry=find(y);// 找根节点if(rx==ry)return;fa[rx]=ry;// 这里将x集合合并到y集合// x到ry = x到rx + rx到ry = d[x]+d[rx]// y到ry = d[y]// 而x到y是w 所以d[x]+d[rx]-d[y] = wd[rx]=w+d[y]-d[x]}

例题:P1196 银河英雄传说
题意:n nn个队列两种操作:

将i ii所在队列接到j jj的尾部
查询i , j i,ji,j是否同一队列输出间隔节点数

解法:
维护d [ x ] d[x]d[x]为x xx到队列头节点的距离,s z [ x ] sz[x]sz[x]为以x xx为根的集合大小用于更新距离

#include<bits/stdc++.h>usingnamespacestd;#definerdread()#defineintlonglong#defineputc(a)putchar(a)#defineenterputchar('\n')#definefo(a,b,c)for(inta=b;a<=c;a++)constintN=3e4+7,INF=0x3f3f3f3f3f3f3f3f;intread(){intx=0,f=1;charch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}returnx*f;}intT,n=3e4+4;intf[N],sz[N];intd[N];intfind(intx){if(f[x]==x)returnx;introot=find(f[x]);d[x]+=d[f[x]];returnf[x]=root;}// 将x合并到yvoidmerge(intx,inty){intxx=find(x),yy=find(y);f[xx]=yy;//将x合并到yd[xx]=sz[yy];//xx到yy的距离 就是原来yy队列的长度sz[yy]+=sz[xx];// yy队列加上了xx队列长度}intres(intx,inty){intxx=find(x),yy=find(y);if(xx!=yy)return-1;returnabs(d[x]-d[y])-1;}signedmain(){T=rd;fo(i,1,n)sz[i]=1,d[i]=0,f[i]=i;while(T--){charop;intx,y;scanf(" %c",&op);x=rd;y=rd;if(op=='M'){merge(x,y);}else{intans=res(x,y);printf("%lld\n",ans);}}return0;}

扩展域并查集

扩展并查集用于处理多种对立关系例如:

食物链 (A吃B B吃C C吃A)
敌人的敌人是朋友 (敌人朋友关系)

它不需要权值的计算而是把每个元素分成很多个域用其连通关系表示约束然后维护每个域的连通性这么讲很难懂讲个题
例题:P2024 [NOI2001] 食物链

我们把并查集分为三个域:

x xx同类域:x xx
x xx吃域:x + n x+nx+n
x xx被吃域:x + 2 ∗ n x+2*nx+2∗n

然后我们来根据题目操作维护它们的关系详见代码:

#include<bits/stdc++.h>usingnamespacestd;#definerdread()#defineintlonglong#defineputc(a)putchar(a)#defineenterputchar('\n')#definefo(a,b,c)for(inta=b;a<=c;a++)constintN=1e6+4,INF=0x3f3f3f3f3f3f3f3f;intread(){intx=0,f=1;charch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}returnx*f;}intn,k;intf[3*N],sz[3*N];/* 1~n 同类 n+1~2n 吃域 2n+1~3n 被吃域 *///常规find和merge操作intfind(intx){//find简写returnf[x]==x?x:f[x]=find(f[x]);}voidmerge(intx,inty){x=find(x);y=find(y);if(x==y)return;// 启发式合并 小集合合并到大集合 可以不管if(sz[x]>sz[y])swap(x,y);f[x]=y;// 将x合并到ysz[y]+=sz[x];}signedmain(){n=rd;k=rd;// 初始化fo(i,1,n*3)f[i]=i,sz[i]=1;intans=0;//假话个数fo(i,1,k){intop,x,y;op=rd;x=rd;y=rd;if(x>n||y>n){ans++;continue;}if(op==1){// xy是同类//y域不能在x的吃域中 x域不能在y的吃域中if(find(x+n)==find(y)||find(y+n)==find(x)){ans++;continue;}//由于它们是同类 故各个域都连通merge(x,y);merge(x+n,y+n);merge(x+2*n,y+2*n);}else{//x吃y//xy不能为同类 x域不能在y的吃域if(find(x)==find(y)||x==y||find(y+n)==find(x)){ans++;continue;}merge(x+n,y);//x吃域加上y域merge(x,y+2*n);//y被吃域加上x域merge(x+2*n,y+n);//x被吃域加上y吃域 (根据食物链题意)}}printf("%lld",ans);return0;}