这里find函数
int find(int x)
{
if (p[x] != x)
{
int root = find(p[x]);
d[x] += d[p[x]];//加上当下根节点的距离
p[x] = root;
}
return p[x];
}

如果合并两个不在一个的连通块的点
if (pa != pb)
{
d[pa] = size[pb]//a的根节点pa从0到size[pb]
s[pb] += s[pa]//加总数
p[pa] = pb;
}

C++ 代码

//1.不问间隔多少战舰->并查集
//2.同时维护间隔多少战舰
//统一维护战舰到排头的距离

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 30010;

int T;
int p[N], s[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()
{
    for (int i = 1; i < N; i ++ )
    {
        p[i] = i;
        s[i] = 1;
    }

    cin >> T;
    while (T -- )
    {
        char c[2];
        int a, b;
        scanf("%s%d%d", c, &a, &b);
        int pa = find(a), pb = find(b);
        if (c[0] == 'M')
        {
            if (pa != pb)
            {
                d[pa] = s[pb];
                s[pb] += s[pa];
                p[pa] = pb;
            }
        }
        else
        {
            if (pa != pb) cout << -1 << endl;
            else printf("%d\n", max(0, abs(d[a] - d[b]) - 1));
        }
    }
}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla