P1196 [NOI2002] 银河英雄传说 （并查集 合并

添加链接描述

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+9;
int fa[N],sum[N],front[N];
int find(int x){
    
    if(x==fa[x])return fa[x];
    int fn=find(fa[x]);//先找到根
    front[x]+=front[fa[x]];//合并他的父节点
    return fa[x]=fn;//返回
}
int main(){
    
    for(int i=1;i<=5e5;i++){
    
        fa[i]=i;
        sum[i]=1;
        front[i]=0;
    }
    int T;
    cin>>T;
    while(T--){
    
        char ch;
        cin>>ch;
        int a,b;
        cin>>a>>b;
        if(ch=='M'){
    
            
            a=find(a),b=find(b);
            if(a!=b){
    
                front[a]+=sum[b];//a的前面加上b的队伍
                sum[b]+=sum[a];//b的队伍加上后面跟的a
                sum[a]=0;//!!a为0
                fa[a]=b;//合并
            }
        }
        else {
    
            if(find(a)==find(b)){
    
                cout<<abs(front[a]-front[b])-1<<"\n";
            }
            else cout<<"-1\n";
        }
        
    }


    return 0;
}