对此题代码实现有个小问题,必关
查看原帖
对此题代码实现有个小问题,必关
920406
违规用户名920406楼主2025/1/4 14:55

带权并查集模板,这是第一篇题解的代码

#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++!

2025/1/4 14:55
加载中...