银河英雄传说

原题链接

分析

分析题目后，我们可以 知道，我们要求的就是，维护并查集中每个元素到根节点的距离，同时维护集合的大小。

第一个需要解决的问题

如何维护当前战舰到根节点的距离

当我们把一列战舰放b到另一列战舰a后，我们如何更新，另一个队列b中每一个战舰到根节点的距离？

我们维护一个数组d，表示的是x到p[x]的距离，则我们只需将d[pb]=Size[pa]

此时，当我们要计算b中每一个战舰的距离时，随着更新根节点，我们就完成了，到新的根节点的距离的更新。

第二个需要解决的问题

两个战舰的距离判断

1. x!=y ans=abs(d[x]-d[y])-1;
2. x=y ans=0;

ACcode

#include<bits/stdc++.h>
using namespace std;
const int N = 3e4 + 10;
int p[N],Size[N],d[N];

int find(int x)
{
    if(p[x]!=x)
    {
        int root = find(p[x]);
        d[x]+=d[p[x]];
        p[x]=root;
    }
    return p[x];
}

int main()
{
    int T;
    scanf("%d",&T);
    for(int i=1;i<=N;i++) 
    {
        p[i]=i;
        Size[i]=1;
    }
    
    while(T--)
    {
        char op[2];
        int a,b;
        scanf("%s%d%d",op,&a,&b);
        if(op[0]==‘M‘)
        {
            int pa = find(a),pb = find(b);
            if(pa!=pb)
            {
                d[pa]=Size[pb];
                Size[pb]+=Size[pa];
                p[pa]=pb;
            }
        }
        else
        {
            int pa  = find(a),pb = find(b);
            if(pa!=pb) puts("-1");
            else printf("%d\n",max(0,abs(d[a]-d[b])-1));
        }
    }
    return 0;
}

银河英雄传说

原文：https://www.cnblogs.com/aitejiu/p/15173404.html