【并查集】洛谷 P1196 银河英雄传说
2021-03-15 20:53:00 # ACM

题链

边带权并查集，$val[i]$记录编号为i的舰船距离根舰船的距离，合并时如x接到y所在舰队的末尾，$fx$，$fy$为$x$，$y$的根节点，并不是$val[fx] += val[y]$，这里的若不是真正舰队末尾则出错，需要$sum[i]$数组记录某一列舰队的数目，$val[fx] += sum[fy]$;

具体如代码着重部分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <bits/stdc++.h>
#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
//#pragma GCC optimize("O2")
using namespace std;
#define LL long long
#define ll long long
#define ULL unsigned long long
#define ls rt<<1
#define rs rt<<1|1
#define one first
#define two second
#define MS 30009
#define INF 1e18
#define mod 99999997
#define Pi acos(-1.0)
#define Pair pair<LL,LL>
#define eps 1e-9

LL n,m,k;
LL fa[MS];
LL val[MS]; // 编号为i的舰船距根节点距离 
LL sum[MS]; // 记录第i列总舰数 

LL find(LL x){
	if(x != fa[x]){
		LL t = fa[x];
		fa[x] = find(fa[x]);
		val[x] += val[t];
	}
	return fa[x];
}

void merge(LL x,LL y){
	LL fx = find(x);
	LL fy = find(y);
	fa[fx] = fy;
	/**********************/
	val[fx] += sum[fy];
	sum[fy] += sum[fx];
	sum[fx] = 0;
	/**********************/
}

int main(){
	//ios::sync_with_stdio(false);
	for(int i=1;i<=30000;i++) fa[i] = i ,sum[i] = 1;
	cin >> k;
	while(k--){
		char op;
		LL x,y;
		cin >> op >> x >> y;
		if(op == 'M'){
			merge(x,y);
		}
		else{
			if(find(x) != find(y)) printf("-1\n");
			else{
				LL t1 = val[x];
				LL t2 = val[y];
				printf("%lld\n",abs(t1-t2)-1);
			}
		}
	}
	
	return 0;
}

Prev
2021-03-15 20:53:00 # ACM
Next