AcWing 238. 银河英雄传说
原题链接
简单
作者:
郡呈
,
2020-05-25 22:48:20
,
所有人可见
,
阅读 664
/*
d[x]-表示x到p[x]的距离
1.如果不需要问间隔距离-并查集裸题
2.用d[x]统一维护当前战舰到祖宗的距离
3.x到y的距离相当于max(0, abs(d[x]-d[y])-1)
4.如何维护相关数据信息-每次排头当作根节点
d[px] = size[py];
size[py] += size[px];
*/
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 3e4+10;
int p[N], s[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() {
int n;
cin >> n;
for(int i = 1; i < N; i++) {
p[i] = i;
s[i] = 1;
}
for(int i = 0; i < n; i++) {
char op;
int x, y;
cin >> op >> x >> y;
// cout << op << ' ' << x << ' ' << y << endl;
if(op == 'M') {
int px = find(x), py = find(y);
// cout << "1------" << px << "-----" << py << endl;
// cout << "1------" << d[px] << "-----" << d[py] << endl;
d[px] += s[py];
//我觉得这里写成+=更好理解
s[py] += s[px];
p[px] = py;
// cout << "2------" << s[px] << "-----" << s[py] << endl;
// cout << "2------" << d[px] << "-----" << d[py] << endl;
} else {
int px = find(x), py = find(y);
if(px != py) puts("-1");
else {
// cout << "------" << px << "-----" << py << endl;
// cout << "------" << d[px] << "-----" << d[py] << endl;
cout << max(0, abs(d[x] - d[y]) - 1) << endl;
//输出的是x到y的距离,开始搞成px到py的距离了,debug了半天
}
}
}
return 0;
}