作用
以接近O(1)的复杂度合并集合并查询两个元素是否在同一个集合中的简介好用数据结构。
实现
概览
将每个集合视作一棵树，每个节点储存它的父节点。特别地，根节点储存它本身。
初始化
将每个点的父节点都设为它本身。
合并
将其中一个集合的根节点的父节点设为另一个集合的根节点。
查询
看两个点在不在同一个集合中，也就是看两个点的根节点一样不一样。
优化（路径压缩）
其实还可以按秩合并，但那个优化代码量相对较大，并且基本上没有毛用，所以就不讲了。
路径压缩，就是在查询根节点的过程中，把当前节点的父节点直接设为祖先节点，以大大减少合并、查询的时间复杂度。
代码
基础版
只有最基础的初始化、查询、合并功能。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Union_Find_Set{
public:
int n,p[N];
void init(int x){
n=x;
for(int i=1;i<=n;i++){
p[i]=i;
}
}
int find(int x){
if(p[x]!=x)p[x]=find(p[x]);
return p[x];
}
void merge(int a,int b){
a=find(a);b=find(b);
p[a]=b;
}
bool same(int a,int b){
return find(a)==find(b);
}
}ufs;
|
计数版
可以记录每个集合内的元素个数
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
| class Union_Find_Set{
public:
int n,p[N],siz[N];
void init(int x){
n=x;
for(int i=1;i<=n;i++){
p[i]=i;
siz[i]=1;
}
}
int find(int x){
if(p[x]!=x)p[x]=find(p[x]);
return p[x];
}
void merge(int a,int b){
a=find(a);b=find(b);
if(a!=b)siz[b]+=siz[a];
p[a]=b;
}
bool same(int a,int b){
return find(a)==find(b);
}
int size(int x){
return siz[find(x)];
}
}ufs;
|
例题
AcWing240-食物链
Luogu2024-食物链
（这是同一道题~话说洛谷的题号真吉利(～￣▽￣)～）
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
| #include<bits/stdc++.h>
using namespace std;
const int N=1.5e5+5;
class Union_Find_Set{
public:
int n,p[N];
void init(int x){
n=x;
for(int i=1;i<=n;i++){
p[i]=i;
}
}
int find(int x){
if(p[x]!=x)p[x]=find(p[x]);
return p[x];
}
void merge(int a,int b){
a=find(a);b=find(b);
p[a]=b;
}
bool same(int a,int b){
return find(a)==find(b);
}
}ufs;
int n,k;
int d,x,y;
int ans;
int main(){
cin.tie(0);
cin>>n>>k;
ufs.init(n*3);
while(k--){
cin>>d>>x>>y;
if(x>n||y>n){
ans++;
continue;
}
if(d==1){
if(ufs.same(x,y+n)||ufs.same(x+n,y)){
ans++;
continue;
}
ufs.merge(x,y);
ufs.merge(x+n,y+n);
ufs.merge(x+n+n,y+n+n);
}
else{
if(ufs.same(x,y)||ufs.same(x,y+n)){
ans++;
continue;
}
ufs.merge(x+n,y);
ufs.merge(x+n+n,y+n);
ufs.merge(x,y+n+n);
}
}
cout<<ans;
return 0;
}
|
完结撒花o(￣︶￣)o