题目大意
起初有$N$艘战舰,按顺序各占一列。现有两种操作。一种操作让某一列战舰接在另一列战舰后面,一种操作查询两艘战舰间间隔了多少战舰
解题思路
每一列都是一个”链”,链就是一棵树的特殊形态,因此每一列都可看作一个集合,用并查集维护所有列。最初$N$艘战舰构成$N$个集合。在路径压缩的情况下,我们建立一个数组$d$,$d[x]$记录战舰$x$与$p[x]$之间的边的权值。在路径压缩把$x$指向树根的同时,我们把$d[x]$更新为从$x$到树根的路径上的所有边权之和。
蓝书的带权并查集$find$函数这样写,虽然已经习惯了另一种写法,但感觉这种写法对于初学者更有利于理解更新$d[x]$的过程(由树根至叶子逐层更新)
int find(int x)
{
if(x == p[x]) return x;
int root= find(p[x]); //递归计算集合代表
d[x]+=d[p[x]]; //维护d数组,对边权求和
return p[x] = root; //路径压缩
}
具体代码
#include <bits/stdc++.h>
using namespace std;
const int N = 3e4 + 10;
int p[N], s[N], d[N];
int m;
int find(int x) //带权并查集的find函数
{
if (p[x] != x)
{
int root = find(p[x]);
d[x] += d[p[x]];
p[x] = root;
}
return p[x];
}
void merge(int a, int b)
{
int pa = find(a), pb = find(b);
if (pa == pb) //数据加强过了,有点坑
return;
d[pa] = s[pb];
s[pb] += s[pa];
p[pa] = pb;
}
int main()
{
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
cin >> m;
for (int i = 0; i < N; i++) //初始化并查集
p[i] = i, s[i] = 1, d[i] = 0;
while (m--)
{
char op;
int a, b;
cin >> op >> a >> b;
if (op == 'M')
merge(a, b);
else
{
int pa = find(a), pb = find(b);
if (pa != pb)
cout << "-1\n";
else
cout << max(abs(d[b] - d[a]) - 1, 0) << '\n';
}
}
return 0;
}