边带权并查集
简单来说,”边带权“并查集就是在原始并查集的基础上增加“维护每个点到根节点之间的信息”这一功能。并查集的特点就是可以很方便地维护这种带有传递性的信息,而并查集实际上就是由若干棵树构成的集合。当遇到仅与每个点到根节点的信息相关的问题时,边带权并查集是一个不错的思路。
模板题:P1196 [NOI2002] 银河英雄传说
下面代码以该题为例
路径压缩:
il int getfa(int x)
{//边带权并查集的路径压缩
if(fa[x]==x) return x;//找到父节点之后返回
int rt=getfa(fa[x]);//对父节点到树根的路径进行压缩
d[x]+=d[fa[x]];//更新x到父节点之间的路径
return fa[x]=rt;//更新x的父节点
}
合并集合
il void merge(int u,int v)
{//边带权并查集的合并操作
u=getfa(u),v=getfa(v);
fa[u]=v,d[u]=sz[v];//将u合并到v上,并更新u的信息
sz[v]+=sz[u];//更新v的集合大小
}
code:
#include<bits/stdc++.h>
using namespace std;
#define il inline
#define re register
il int read()
{
int s=0,w=1;char c=getchar();
while(c<'0'||c>'9'){ if(c=='-') w=-1;c=getchar();}
while(c>='0'&&c<='9'){ s=(s<<1)+(s<<3)+c-'0';c=getchar();}
return s*w;
}
const int N=3e4+10;
int T,n=3e4;
int fa[N],d[N],sz[N];
il int Abs(int x){ return (x<0)?-x:x;}
il int getfa(int x)
{//边带权并查集的路径压缩
if(fa[x]==x) return x;//找到父节点之后返回
int rt=getfa(fa[x]);//对父节点到树根的路径进行压缩
d[x]+=d[fa[x]];//更新x到父节点之间的路径
return fa[x]=rt;//更新x的父节点
}
il void merge(int u,int v)
{//边带权并查集的合并操作
u=getfa(u),v=getfa(v);
fa[u]=v,d[u]=sz[v];//将u合并到v上,并更新u的信息
sz[v]+=sz[u];//更新v的集合大小
}
il void query(int u,int v)
{
getfa(u),getfa(v);
if(fa[u]!=fa[v]){
printf("-1\n");return;
}
printf("%d\n",Abs(d[u]-d[v])-1);
}
int main()
{
for(re int i=1;i<=n;i++) fa[i]=i,sz[i]=1;
T=read();
while(T--){
char op;
cin>>op;int uu=read(),vv=read();
if(op=='M') merge(uu,vv);
if(op=='C') query(uu,vv);
}
return 0;
}
end