洛谷 P1196 [NOI2002]银河英雄传说

题意简述

有30000列，每列都有一艘战舰，编号1~30000
有2种操作：
1.将一列的战舰运到另一列
2.询问两个战舰是否在同一列，如果是，求出它们之间的距离

题解思路

并查集，
维护每个点x离自己祖先的距离dis[x]，和该点所在集合的大小size[x]
每次查找时更新即可，
点x，y之间距离为abs(dis[x] - dis[y]) - 1

代码

#include <iostream>
using namespace std;
int T, x, y, xx, yy;
int fa[31000], dis[31000], size[31000];
char c;
int abs(int x)
{
	return x > 0 ? x : -x;
}
int gf(int x)
{
	if (x == fa[x]) return x;
	int xxx = fa[x];
	size[x] = size[fa[x] = gf(fa[x])];
	dis[x] += dis[xxx];
	return fa[x];
}
int main()
{
	ios::sync_with_stdio(false);
	cin >> T;
	for (register int i = 1; i <= 30000; ++i)
	{
		fa[i] = i;
		size[i] = 1;
	}
	while (T--)
	{
		cin >> c >> x >> y;
		xx = gf(x);
		yy = gf(y);
		if (c == 'M')
		{
			fa[xx] = yy;
			dis[xx] += size[yy];
			size[yy] = (size[xx] += size[yy]);
		}
		else
		{
			if (xx != yy) cout << -1 << endl;
			else cout << abs(dis[y] - dis[x]) - 1 << endl;
		}
	}
}