AcWing 238. 银河英雄传说
原题链接
简单
作者:
acwing_62485
,
2025-04-16 22:27:33
· 中国香港
,
所有人可见
,
阅读 1
T = int(input())
maxN = 30010
p = [i for i in range(maxN)]
d = [0] * maxN
sz = [1] * maxN # 每一列的战舰数
def find(x):
if p[x] != x:
p[x] = find(p[x])
d[x] += d[p[x]] # 当前节点距离根节点的长度
return p[x]
for _ in range(T):
op, a, b = input().split()
a = int(a)
b = int(b)
if op == 'M':
pa = find(a)
pb = find(b)
if pa != pb:
p[pa] = pb
d[pa] = sz[pb] # 把a整列接到b的尾部
# 只有合并操作会改变sz
sz[pb] += sz[pa] # 更新新集合的大小
else:
if find(a) != find(b):
print(-1)
else:
print(max(0, abs(d[a] - d[b]) - 1))