AcWing 238. 银河英雄传说
原题链接
简单
作者:
罪
,
2021-01-02 15:29:25
,
所有人可见
,
阅读 476
C++ 代码
#include <iostream>
#include <cmath>
using namespace std;
const int N = 30010;
int t;
int p[N], d[N], s[N];//p[N]维护集合中结点的关系/d[N]维护结点之间的距离/s[N]维护集合中结点个数
int find(int x)
{
if (p[x] == x) return x;
int root = find(p[x]);
d[x] += d[p[x]];
return p[x] = root;
}
void merge(int x, int y)
{
int p_x = find(x), p_y = find(y);//找到x,y的祖先结点
p[p_x] = p_y;//将x祖先的祖先结点成为y祖先的子结点
d[p_x] = s[p_y];//更新p_x结点到p_y结点之间的距离(即p_x和p_y结点之间的战舰个数)
s[p_y] += s[p_x];//更新以p_y为根结点的集合中结点的个数(即战舰的个数)
}
int main()
{
scanf("%d", &t);
for (int i = 1; i <= N; i ++ )
{
p[i] = i;
s[i] = 1;
}
while (t -- )
{
char op[2];
int i, j;
scanf("%s%d%d", op, &i, &j);
if (op[0] == 'M') merge(i, j);
else
{
if (find(i) == find(j)) printf("%d\n", abs(d[i] - d[j]) - 1);
else printf("-1\n");
}
}
return 0;
}