带权并查集模板,这是第一篇题解的代码
#include<bits/stdc++.h>
using namespace std;
int fa[30001],front[30001],num[30001],x,y,i,j,n,T,ans; //fa[i]表示飞船i的祖先
//front[i]表示飞船i与其所在列队头的距离
//num[i]表示第i列的飞船数量
char ins;
int find(int n){ //查找祖先的函数
if(fa[n]==n)return fa[n];
int fn=find(fa[n]); //先递归找到祖先
front[n]+=front[fa[n]]; //在回溯的时候更新front(因为更新时要用到正确的front[祖先] 第10行
//所以只能在回溯的时候更新)
return fa[n]=fn;
}
int main(){
cin>>T;
for(i=1;i<=30000;++i){ //定初值
fa[i]=i;
front[i]=0;
num[i]=1;
}
while(T--){
cin>>ins>>x>>y;
int fx=find(x); //fx为x所在列的队头 第23行
int fy=find(y); //fy同上 第24行
if(ins=='M'){
front[fx]+=num[fy]; //更新front[x所在列队头(现在在y所在队列后面)] 第26行
//即加上y所在队列的长度
fa[fx]=fy; //将fy设为fx的祖先
num[fy]+=num[fx]; //更新以fy为队头队列的长度
num[fx]=0; //以fx为队头的队列已不存在,更新
}
if(ins=='C'){
if(fx!=fy)cout<<"-1"<<endl; //若x和y的祖先不相同,则不在同一列
else cout<<abs(front[x]-front[y])-1<<endl; //否则利用x和y离队头的距离算
//出它们的距离
}
}
return 0;
}
代码中标记了几行
问题1:10行对front数组的修改有亿点道理,但23,24行可能会造成重复修改吗?这个代码是怎么避免的?
问题2:26行的修改也有亿点道理,但是它会不会影响find函数的修改?
祝各位大佬2025省选RP++!