CQUOJ 21465 部落Mod(并查集、删点 | 启发式合并)

题意:

$N\le 10^5个点,M\le 10^6个操作$
$U a b:合并a,b$
$D a:移除a所在的集合关系$
$S a:询问a所在的集合大小$
$F a b:询问a和b是否在同一集合$

分析:

$暴力的做法就直接不路径压缩,只按秩合并保证树高,同时用set维护每棵子树的元素$
$对于D操作,直接暴力遍历根节点的set重建,看起来复杂度很高$
$实际均摊分析一下,暴力重建操作与树大小有关,树的大小与操作次数有关$
$相当于把重建操作均摊到每一次建立操作上了$
$按秩启发式合并加上set的复杂度,使得每次复杂度是log^2 n的$
$总时间复杂度为O(mlog^2n)$

代码:

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
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
//
// Created by TaoSama on 2016-05-07
// Copyright (c) 2016 TaoSama. All rights reserved.
//
#pragma comment(linker, "/STACK:102400000,102400000")
#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <string>
#include <set>
#include <vector>
using namespace std;
#define pr(x) cout << #x << " = " << x << " "
#define prln(x) cout << #x << " = " << x << endl
const int N = 1e5 + 10, INF = 0x3f3f3f3f, MOD = 1e9 + 7;
int n, m;
struct DSU {
int n, p[N];
set<int> s[N];
void init(int _n) {
n = _n;
for(int i = 1; i <= n; ++i) resume(i);
}
void resume(int i) {
p[i] = i;
s[i].clear();
s[i].insert(i);
}
int find(int x) {
return p[x] == x ? x : find(p[x]);
}
void del(int x) {
x = find(x);
for(auto u : s[x]) {
if(u == x) continue;
resume(u);
}
resume(x);
}
void unite(int x, int y) {
x = find(x), y = find(y);
if(x == y) return;
if(s[x].size() > s[y].size()) swap(x, y);
p[x] = y;
for(auto u : s[x]) s[y].insert(u);
}
int size(int x) {
x = find(x);
return s[x].size();
}
bool same(int x, int y) {
x = find(x), y = find(y);
return x == y;
}
} dsu;
int main() {
#ifdef LOCAL
freopen("C:\\Users\\TaoSama\\Desktop\\in.txt", "r", stdin);
// freopen("C:\\Users\\TaoSama\\Desktop\\out.txt","w",stdout);
#endif
ios_base::sync_with_stdio(0);
clock_t _ = clock();
int t; scanf("%d", &t);
while(t--) {
scanf("%d%d", &n, &m);
dsu.init(n);
while(m--) {
char op[2];
int x, y; scanf("%s%d", op, &x);
if(*op == 'U') {
scanf("%d", &y);
dsu.unite(x, y);
} else if(*op == 'D') dsu.del(x);
else if(*op == 'S') printf("%d\n", dsu.size(x));
else {
scanf("%d", &y);
puts(dsu.same(x, y) ? "Yes" : "No");
}
}
}
#ifdef LOCAL
printf("\nTime cost: %.2fs\n", 1.0 * (clock() - _) / CLOCKS_PER_SEC);
#endif
return 0;
}


$事实上有更加优美的做法,$并查集删点
$事实对于D操作,可以直接把这棵子树连到其它地方去,比如用0当作废弃点$
$对于重新合并的时候,直接rehash这个节点的id,这样之前的“废弃树”结构没变,这个点也新建了$
$非常完美的姿势做法,就是空间复杂度等于操作复杂度了,由于rehash这个原因$
$时间复杂度O(m\alpha(n)),空间复杂度O(m)$

代码:

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
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
//
// Created by TaoSama on 2016-05-07
// Copyright (c) 2016 TaoSama. All rights reserved.
//
#pragma comment(linker, "/STACK:102400000,102400000")
#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <string>
#include <set>
#include <vector>
using namespace std;
#define pr(x) cout << #x << " = " << x << " "
#define prln(x) cout << #x << " = " << x << endl
const int N = 2e6 + 10, INF = 0x3f3f3f3f, MOD = 1e9 + 7;
int n, m;
struct DSU {
int n, tim, id[N], p[N], sz[N];
void init(int _n) {
n = _n; tim = 0;
for(int i = 0; i <= n; ++i) resume(i);
}
int resume(int i) {
id[i] = tim;
p[tim] = tim;
sz[tim] = 1;
return tim++;
}
int find(int x) {
return p[x] = p[x] == x ? x : find(p[x]);
}
int findResume(int x) {
int y = id[x];
int fa = find(y);
if(fa == 0) return resume(x);
return fa;
}
void unite(int x, int y) {
x = findResume(x), y = findResume(y);
if(x == y) return;
p[x] = y;
sz[y] += sz[x];
}
void del(int x) {
x = findResume(x);
p[x] = 0;
}
int size(int x) {
return sz[findResume(x)];
}
bool same(int x, int y) {
return findResume(x) == findResume(y);
}
} dsu;
int main() {
#ifdef LOCAL
freopen("C:\\Users\\TaoSama\\Desktop\\in.txt", "r", stdin);
// freopen("C:\\Users\\TaoSama\\Desktop\\out.txt","w",stdout);
#endif
ios_base::sync_with_stdio(0);
clock_t _ = clock();
int t; scanf("%d", &t);
while(t--) {
scanf("%d%d", &n, &m);
dsu.init(n);
while(m--) {
char op[2];
int x, y; scanf("%s%d", op, &x);
if(*op == 'U') {
scanf("%d", &y);
dsu.unite(x, y);
} else if(*op == 'D') dsu.del(x);
else if(*op == 'S') printf("%d\n", dsu.size(x));
else {
scanf("%d", &y);
puts(dsu.same(x, y) ? "Yes" : "No");
}
}
}
#ifdef LOCAL
printf("\nTime cost: %.2fs\n", 1.0 * (clock() - _) / CLOCKS_PER_SEC);
#endif
return 0;
}


1. 除非注明,本博文即为原创,转载请注明链接地址
2. 本博文只代表博主当时的观点或结论,请不要恶意攻击
3. 如果本文帮到了您,不妨点一下 下面分享到 按钮,让更多的人看到