题目链接 238. 银河英雄传说

并查集求每个节点到祖宗节点的距离 + 并查集求每个并查集中点的数量

并查集求每个节点到根节点的距离可以参考 AcWing 240. 食物链

并查集求每个并查集中点的数量可以参考 AcWing 1252. 搭配购买

并查集

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 30010;
int d[N];  //记录根节点
int sized[N];  //记录当前并查集中元素的个数
int pa[N];
int m;

int find(int x)
{
    if (pa[x] != x)
    {
        int root = find(pa[x]);  
        d[x] += d[pa[x]];//递归到最底层（根节点的下面一个节点），然后将路径长度一段一段加起来
        pa[x] = root;  //压缩一下路径
    }
    return pa[x];
}

int main(){
    scanf("%d", &m);

    for(int i = 1;i < N;++i){
        pa[i] = i;
        sized[i] = 1;
    }
    while (m -- )
    {
        char op[2];
        int a, b;
        scanf("%s%d%d", op, &a, &b);
        if (op[0] == 'M')
        {
            int fa = find(a), fb = find(b);
            d[fa] = sized[fb];  //pa到pb的距离即为pb连通块的大小
            sized[fb] += sized[fa];
            pa[fa] = fb;
        }
        else
        {
            int fa = find(a), fb = find(b);
            if (fa != fb) puts("-1");
            else printf("%d\n", max(0, abs(d[a] - d[b]) - 1));
        }
    }
    return 0;
}