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;
}