P1196 [NOI2002] 银河英雄传说 带权并查集

P1196 [NOI2002] 银河英雄传说

使用带权并查集维护:

  1. 每个战舰所属列。
  2. 每个战舰到当前列第一个战舰的距离。
  3. 每列的战舰数量。
  • 如何求同列战舰之间相隔的战舰数量?

    使用两战舰到当前列头部的距离之差减1即可得到。

  • 如何在并查集合并时维护每个战舰到当前列第一个战舰的距离?

    当前点到当前点合并前的祖先的距离与祖先到链头的点距离相加,在find祖先递归的回溯过程中更新(只有find操作路径压缩会改变祖先)。

  • 每一次合并操作:把x的祖先(链头)插到y的链尾后面,更新x原链头到现链头(y链头)的距离,更新y所在列的大小。

    注意每次把x合并到y后面时,x的祖先就要变成y的祖先,顺序不能反,否则会打乱维护的2、3性质。

/*P1196 [NOI2002] 银河英雄传说
使用带权并查集维护:1.每个战舰所属列 2.每个战舰到当前列第一个战舰的距离 3.每列的战舰数量
- 如何求同列战舰之间相隔的战舰数量?使用两战舰到当前列头部的距离之差减1即可得到。
- 如何在并查集合并时维护每个战舰到当前列第一个战舰的距离?
  当前点到当前点合并前的祖先的距离与祖先到链头的点距离相加,在find祖先递归的回溯过程中更新(只有find操作路径压缩会改变祖先) 
- 每一次合并操作:把x的祖先(链头)插到y的链尾后面,更新x原链头到现链头(y链头)的距离,更新y所在列的大小 
	注意每次把x合并到y后面时,x的祖先就要变成y的祖先,顺序不能反,否则会打乱维护的2、3性质
*/
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=100000;
int f[N],dis[N],siz[N];//并查集;到链头的距离;当前链的长度
int find(int x)//每次查询会更改祖先,必须维护dis 
{
	if(f[x]==x) return x;
	int fu=find(f[x]);
	dis[x]+=dis[f[x]];//原来dis存的是它到自己原来祖先(f[x])的距离,现在只需要加上其祖先到链头的距离
	return f[x]=fu; 
}
int main()
{
	for(int i=1;i<=30000;i++) f[i]=i,siz[i]=1;
	int t,x,y;
	char op;
	scanf("%d",&t);
	while(t--)
	{
		cin>>op; 
		scanf("%d%d",&x,&y);
		int fx=find(x),fy=find(y);
		if(op=='M')
		{
			dis[fx]+=siz[fy];//x的祖先(链头)插到y的链尾后面,x原链头到现链头(y链头)距离更新
			f[fx]=fy;//x合并到y后面,x的祖先变成y的祖先,顺序不能反
			siz[fy]+=siz[fx];//更新y所在列的大小 
			siz[fx]=0;//清零实际上可有可无, 
		}
		if(op=='C')
		{
			if(fx!=fy) printf("-1\n");
			else printf("%d\n",abs(dis[x]-dis[y])-1);
		}
	}
	return 0;
}

热门相关:洪荒二郎传   神算大小姐   修真界败类   神算大小姐   3位娃娃脸韩国新人首次亮相