并查集总结
作者:
流动的音符
,
2023-11-25 18:03:45
,
所有人可见
,
阅读 85
//带权并查集
/*
假如让z,y属于同一类,可以a->z==0
a-->z==1属于另外一类
*/
int find(int x){
if(x!=p[x]){
int u=find(p[x]);
len[x]+=len[p[x]];
p[x]=u;
}
return p[x];
}
int tz=find(z),ty=find(y);
/* tz ty
^ ^
| 1 |
z <------ y
更新tz到ty的距离
len[tz]=-len[z]-1+len[y];
p[tz]=ty;
*/
//并查集头跟尾巴 siz[i],i后面跟着的结点数量
if(s=='M'){//让z跟在y后面
if(tz==ty) continue;
p[tz]=ty;
len[tz]=siz[ty];//tz到根节点距离变成ty后面数量
siz[ty]+=siz[tz];//ty节点后面数量加上tz
}else{
if(tz!=ty){cout<<"-1\n";continue;}
int ti=max(abs(len[z]-len[y])-1,0);
cout<<ti<<endl;
//z前面有多少结点, z与y之间的结点数量
}
//扩展域并查集
const int N = 2e4 + 10, Base = N / 2;
int yz=find(z+base),yy=find(y+base);
/*一部分属性在N/2左边,另外在右边
如果z与y属性相同,那么他们的异域属性也相同*/
if(find(yz)==fidn(y)) {//异域应该相反
break;
}
p[tz]=ty;
p[yz]=yy;
/*如果z与y属性相反,那么他们与对方异域属性相同*/
if(find(a)==find(b)) break;
//a的异域等于b 将他们放在同一个集合
//a等于b的异域
p[yz]=y
p[z]=yy;
/*敌人的敌人是朋友
a的敌人都在n+a集合里面
if(a,b)是敌人
那么 a与n+b是一个集合,(敌人的敌人是朋友)
b与n+a是一个集合。*/
/*连通块问题*/
初始都没有连通,那么一共num=n个块;
if(find(z)!=find(y)) num--;//连通一个块
//字符串并查集,初始就是"",此时无父亲
/*单向并查集*/
用floyed等,把i到j更新最终模式,此时链接i到j
那么p[j]=p[i],j的父亲就是i
for(int i=1;i<=n;i++)
if(p[i]==i) 连通块+1
/*
在空间坐标系中,只用看z坐标即可,把每一个坐标,缩成一个点。
然后遍历每一个点与其他点,如果球相切或者相交,那么他们的就可以
放在一个集合里面。
坐标化成1-n个点,最低点是0,最高点是n+1,最后看0与n+1是否连通
*/