【NOI2002】【Luogu1196】银河英雄传说(并查集带边权)

            

problem

  • 有30000条队列,初始每条队列一条战舰,编号为1-30000。
  • 给出T条指令,分为合并和询问,
    1、合并指令为: M i j 含义为第i号战舰所在的整个战舰队列,作为一个整体(头在前尾在后)接至第j号战舰所在的战舰队列的尾部。
    2、询问指令为: C i j 该指令意思是,询问电脑,第i号战舰与第j号战舰当前是否在同一列中,如果在同一列中,那么它们之间布置有多少战舰。

solution

  • 并查集维护战舰集合。
  • 记录size表示战舰所在队列大小。
  • 记录ranks表示某战舰到父亲之间战舰的个数。
  • 合并时a,b时,令ranks[b]=size[a]。

codes

//带权并查集,维护每个节点(战舰)到该列舰首的位置和每列战舰的长度
#include
#include
#define maxn 30000+10
using namespace std;
int size[maxn], ranks[maxn];
int fa[maxn];
int find(int x){
    if(fa[x] == x)return x;
    int t = find(fa[x]);
    ranks[x] += ranks[fa[x]]; //路径压缩时需要更新当前位置
    return fa[x] = t;
}
void merge(int x, int y){
    int a = find(x), b = find(y);
    fa[a] = b; //x整列接到y后面
    ranks[a] += size[b];//x的首元素位置加上y的长度
    size[b] += size[a];//b的长度加上a的长度
    size[a] = 0;
}
int main(){
    int n = 30000, m;
    for(int i = 1; i <= n; i++)fa[i] = i;
    for(int i = 1; i <= n; i++)size[i] = 1;
    cin>>m;
    for(int i = 1; i <= m; i++){
        char ch;  int a, b;
        cin>>ch>>a>>b;
        if(ch == 'M'){
            merge(a,b);//a整列接到b后面
        }else{
            if(find(a)!=find(b))cout<<-1<<"\n";
            else cout<<abs(ranks[a]-ranks[b])-1<<"\n";
        }
    }
    return 0;
}
点赞

发表评论

昵称和uid可以选填一个,填邮箱必填(留言回复后将会发邮件给你)
tips:输入uid可以快速获得你的昵称和头像