AcWing
  • 首页
  • 活动
  • 题库
  • 竞赛
  • 应用
  • 更多
    • 题解
    • 分享
    • 商店
    • 问答
    • 吐槽
  • App
  • 登录/注册

AcWing 238. 银河英雄传说(算法提高课) 0.04 AC币

作者: 作者的头像   fangy ,  2023-03-16 18:13:53 ,  所有人可见 ,  阅读 6


0


#include <iostream>

using namespace std;

const int N = 300010;

int n, m;
int p[N], d[N], sz[N];

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

int main()
{
    cin >> m;

    for (int i = 1; i <= N; ++i) p[i] = i, sz[i] = 1;

    while (m--)
    {
        char op[2];
        int x, y;
        scanf("%s%d%d", op, &x, &y);

        int px = find(x), py = find(y);

        if (op[0] == 'M')
        {
            if (px != py) p[px] = py, d[px] = sz[py], sz[py] += sz[px];
        }
        else 
        {
            int distance = -1;
            if (px == py) distance = max(0, abs(d[x] - d[y]) - 1);
            printf("%d\n", distance);
        }
    }

    return 0;
}

0 评论

你确定删除吗?
1024
x

© 2018-2023 AcWing 版权所有  |  京ICP备17053197号-1
用户协议  |  隐私政策  |  常见问题  |  联系我们
AcWing
请输入登录信息
更多登录方式: 微信图标 qq图标
请输入绑定的邮箱地址
请输入注册信息