[NOI2002] 银河英雄传说(并查集)
2023-12-17 22:24:58
题目链接
活动 - AcWing本活动组织刷《算法竞赛进阶指南》,系统学习各种编程算法。主要面向有一定编程基础的同学。https://www.acwing.com/problem/content/240/
代码
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 30010;
int m;
int p[N], sz[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()
{
scanf("%d", &m);
for (int i = 1; i < N; i++)
{
p[i] = i;
sz[i] = 1;
}
while (m--)
{
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] = sz[pb];
sz[pb] += sz[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;
}
参考资料
- AcWing算法提高课
文章来源:https://blog.csdn.net/u012181348/article/details/135051327
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!