并查集—合并集合

并查集可以表示元素中的属于状态,比较重要。其核心元素是father数组,初始化如下:

1
2
3
4
5
void init() {
for(int i = 0; i < n; i++) {
father[i] = i
}
}

另外就是查找元素x的父亲:

1
2
3
4
5
6
7
8
9
10
//普通版
int find(int x) {
while(x != father[x]){
x = father[x];
}
}
//路径压缩优化(推荐)
int find(int x) {
return x == father[x] ? x : find(father[x]);
}

合并集合:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//普通版
void merge(int a, int b) {
a = find(a), b = find(b);
if(find(a) != find(b)) father[b] = a;
}

//启发式合并,即将矮树合并到高树
void merge(int a, int b) {
a = find(a), b = find(b);
//如果a的父亲的高度小于b的父亲的高度
if(rank[a] <= rank[b]) father[a] = b;
else father[b] = a;
//如果两树的高度是不同的,且a和b的父亲不相同,那就要更新高度。否则整体树的高度是不变的(画图可以看出)
if(rank[a] != rank[b] && a != b) rank[b]++;
}

Acwing

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
#include <iostream>
using namespace std;
const int MAXN = 100010;
char mode;
int a, b, n, t;
// 并查集,树的高度数组(rank数组)
int father[MAXN], rk[MAXN];

void init() {
// 高度初始化为1
for(int i = 0; i < n; i++) father[i] = i, rk[i] = 1;
}

// 递归法可以压缩路径
int find(int x) {
return x == father[x] ? x : find(father[x]);
}

// 启发式合并 = 按树的高度合并
void merge(int a, int b) {
// 找爹
int fathera = find(a), fatherb = find(b);
// 如果a的爹的高度小于等于b的爹的高度(把a的爹合并到b的爹)即将矮的树合并到高的树
if (rk[fathera] <= rk[fatherb]) father[fathera] = fatherb;
else father[fatherb] = fathera;
// 只有在两个树的高度相同的时候,才会更新树的高度。不然高度是不变的。
if (rk[fathera] == rk[fatherb] && fathera != fatherb) rk[fatherb] ++;
}

int main() {
cin >> n >> t;
init();
while(t--) {
cin >> mode >> a >> b;
if(mode == 'M') {
merge(a, b);
} else {
if(find(a) == find(b)) cout <<"Yes\n";
else cout << "No\n";
}
}
}
Author

InverseDa

Posted on

2021-03-12

Updated on

2023-03-30

Licensed under

Comments

Your browser is out-of-date!

Update your browser to view this website correctly.&npsb;Update my browser now

×