238. 银河英雄传说

题目链接：https://www.acwing.com/problem/content/240/

思路

是否在同一个集合很好维护，边带权记录某个节点到祖先(列的第一个节点)的距离就好。 然后查询两个节点的间隔就是：abs(w[a]-w[b])-1

代码

#include<bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define debug  freopen("in.txt","r",stdin),freopen("out.txt","w",stdout);
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 1e6+10;
using namespace std;

int T;
int fa[maxn],w[maxn],sz[maxn];

void init(){
    for(int i = 1;i<=30000;i++) fa[i] = i;
    for(int i = 1;i<=30000;i++) sz[i] = 1;
}
int find(int x){
    if(fa[x] != x){
        int f = fa[x];
        fa[x] = find(fa[x]);
        w[x] += w[f];
    }
    return fa[x];
}
void join(int x,int y){
    int fx = find(x),fy = find(y);
    if(fx!=fy){
        fa[fx] = fy;
        w[fx] = sz[fy];
        sz[fy] += sz[fx];
        sz[fx] = 0;
    }
}

int main(){
    // debug;
    ios;
    init();
    cin>>T;    
    char op;int a,b;
    while(T--){
        cin>>op>>a>>b;
        if(op == 'M'){
            join(a,b);
        }else{
            if(find(a) != find(b)) cout<<-1<<'\n';
            else {
                cout<<abs(w[a] - w[b])-1<<'\n';
            }
        }
    }



    return 0;
}