AcWing 238. 银河英雄传说
原题链接
简单
作者:
萨满
,
2021-03-11 17:21:29
,
所有人可见
,
阅读 309
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;
const int N = 30010;
int T;
int p[N], d[N], sz[N]; // size 集合的大小 d 到根结点的距离
int find(int x)
{
if (p[x] != x)
{
int t = find(p[x]); // t暂存p[x]的祖宗结点(也是x的祖宗结点)
d[x] += d[p[x]]; // x->p[x]距离 + p[x]->祖宗结点距离 d[x]更新为x到祖宗结点的距离
p[x] = t; // p[x]指向x的祖宗结点
}
return p[x];
}
int main()
{
cin >> T;
for (int i = 1; i <= N; i ++ ) p[i] = i, sz[i] = 1;
while (T --)
{
char op[2];
int a, b;
cin >> op >> a >> b;
if (op[0] == 'M')
{
int pa = find(a), pb = find(b);
p[pa] = pb; // 第i号战舰所在列接在第j号战舰所在列后 pa->pb
d[pa] = sz[pb]; // pa->pb距离为pb这一列的size
sz[pb] += sz[pa];
}
else if (op[0] == 'C')
{
int pa = find(a), pb = find(b);
if (p[pa] != p[pb]) cout << -1 << endl;
else
{
cout << abs(d[a] - d[b]) - 1 << endl; // -1 输出的是第i号战舰与第j号战舰之间布置的战舰数目
}
}
}
return 0;
}