文章

25

粉丝

0

获赞

0

访问

68451

头像
边带权并查集
经验总结
发布于2020年4月19日 22:19
阅读数 2085

银河英雄传说:

#include<iostream>
#include<cmath>
using namespace std;
int n;
const int N = 31010;
int father[N], d[N], size[N];
int find(int x){
	if (father[x]!=x){
		int root = find(father[x]);
		d[x] += d[father[x]];
		father[x] = root;
	}
	return father[x];
}
void union_set(int x,int y){
	x = find(x); y = find(y);
	father[x] = y;
	d[x] = size[y];
	size[y] += size[x];
}
int main(){
	scanf("%d\n", &n);
	for (int i = 0; i <= 30000; i++){
		father[i] = i;
		size[i] = 1;
		d[i] = 0;
	}
	for (int i = 0; i < n; i++){
		char ch = getchar();
		int u, v;
		scanf("%d %d\n", &u, &v);
		if (ch == 'M'){
			union_set(u, v);
		}
		else{
			if (find(u) == find(v)){
				printf("%d\n", abs(d[u] - d[v]) - 1);
			}
			else{
				printf("-1\n");
			}
		}
	}

	return 0;
}

 



登录后发布评论

暂无评论,来抢沙发