摘要
Title: 238. 银河英雄传说
Tag: 并查集
Memory Limit: 64 MB
Time Limit: 1000 ms

238. 银河英雄传说

题意

有一个划分为 N列的星际战场，各列依次编号为 1,2,…,N
有 N艘战舰，也依次编号为 1,2,…,N，其中第 i号战舰处于第 i列。
有 T条指令，每条指令格式为以下两种之一：
M i j，表示让第 i号战舰所在列的全部战舰保持原有顺序，接在第 j号战舰所在列的尾部。
C i j，表示询问第 i号战舰与第 j号战舰当前是否处于同一列中，如果在同一列中，它们之间间隔了多少艘战舰。
现在需要你编写一个程序，处理一系列的指令。
思路

并查集——边带权的例题
B站讲解录像！

代码

/*
* @Author: NEFU AB-IN
* @Date: 2023-02-20 21:51:02
* @FilePath: \Acwing\238\238.cpp
* @LastEditTime: 2023-02-21 11:27:22
*/
#include <bits/stdc++.h>
using namespace std;
#define int long long
#undef int

#define SZ(X) ((int)(X).size())
#define ALL(X) (X).begin(), (X).end()
#define IOS                                                                                                            \
    ios::sync_with_stdio(false);                                                                                       \
    cin.tie(nullptr);                                                                                                  \
    cout.tie(nullptr)
#define DEBUG(X) cout << #X << ": " << X << '\n'
typedef pair<int, int> PII;

const int N = 1e5 + 10, INF = 0x3f3f3f3f;

int fa[N], d[N], sz[N];

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

signed main()
{
    IOS;
    int t;
    cin >> t;
    for (int i = 1; i < N; ++i)
    {
        fa[i] = i;
        sz[i] = 1;
    }

    while (t--)
    {
        char q;
        int a, b;
        cin >> q >> a >> b;
        int ra = find(a), rb = find(b);
        if (q == 'M')
        {
            if (ra != rb)
            {
                fa[ra] = rb;
                d[ra] = sz[rb];
                sz[rb] += sz[ra];
            }
        }
        else
        {
            if (ra != rb)
                cout << "-1\n";
            else
                cout << max(0, abs(d[a] - d[b]) - 1) << '\n';
        }
    }
    return 0;
}

238. 银河英雄传说

题意

思路

代码