UVA11987

题目:UVA11987
或者看题目PDF
题目很直截了当说了并查集 不过这里的并查集和我们一般接触的并查集有点不一样
一般的并查集无非是两种操作:find merge,顶多加个按秩合并和路径压缩
这里多了一个删点操作
题目的操作1不多说了 就是普通的merge操作
操作2 把p点从它所在的集合里拿出来 然后把p和q连起来
这里有个问题 我怎么把p从它所在的集合里拿出来
如果我们直接把它拿出来和q连起来 会出现什么情况?
不只是p和q连起来了 p的所有子节点也和q练起来了 这样就有错误
有一个解决方法:不去操作这个p 不改变p所在的整个并查集 然后复制一个新的节点p’ 把p’和q连起来 之后所有对p的操作都改成对p’操作 也就是原来的p节点只是一个虚拟节点 它的作用是维持原并查集的性质 而并不提供题目所要求的sum和num的信息
操作3 用额外的sum和num数组记录并查集的元素和与元素个数
注意的是在删除p节点的时候要更新num和sum信息
代码

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
72
73
74
75
76
77
78
79
80
81
#include<iostream>

using namespace std;

const int MAXN = 1e5 + 10;
int bin[MAXN * 2];
int id[MAXN * 2];
int summ[MAXN * 2];
int num[MAXN * 2];
int cnt, n, m;

void init() {
cnt = n + 1;
for (int i = 1; i <= n; i++) {
bin[i] = id[i] = summ[i] = i;
num[i] = 1;
}
}

int find(int a) {
a = id[a];
while (a != bin[a]) a = bin[a];
return a;
}

void merge(int a, int b) {
a = id[a], b = id[b];
a = find(a);
b = find(b);
if (a == b) return;
bin[b] = a;
summ[a] += summ[b];
num[a] += num[b];
}

void move(int p, int q) {
num[find(id[p])]--;
summ[find(id[p])] -= p;
id[p] = cnt;
id[cnt] = cnt;
num[cnt] = 1;
summ[cnt] = p;
bin[cnt] = cnt;
merge(cnt, id[q]);
cnt++;
}

void sum(int q) {
q = id[q];
q = find(q);
cout << num[q] << ' ' << summ[q] << endl;
}

int main() {
// int begin_time=clock();
while (~scanf("%d %d", &n, &m)) {
init();
for (int i = 1; i <= m; i++) {
int op;
scanf("%d", &op);
if (op == 1) {
int p, q;
scanf("%d %d", &p, &q);
merge(p, q);
}
else if (op == 2) {
int p, q;
scanf("%d %d", &p, &q);
if (find(p) == find(q)) continue;
move(p, q);
}
else if (op == 3) {
int q;
scanf("%d", &q);
sum(q);
}
}
}
// cout<<"time use: "<<clock()-begin_time<<" ms"<<endl;
return 0;
}