并查集

并查集

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
int f[N],w[N]; //w[i] 记录每个以节点i为根的集合中点的数量
int n,m;

void init(){
for(int i=1;i<=n;i++){
f[i] = i;
w[i] = 1;
}
}

int find(int u){
if(u == f[u]) return u;
else return f[u] = find(f[u]);
}

void join(int u,int v){
u = find(u);
v = find(v);
if(u == v) return;
f[u] = v;
w[v] += w[u];
}

bool isSame(int u,int v){
u = find(u);
v = find(v);
return u == v;
}

求图是否连通

连通图

由于如果都连通时,所有点的跟都是一样的,因此以该根的图的节点个数会等于总节点个数。

1
2
3
4
5
int fa = find(1);
if(w[fa] == n) cout << "YES" << "\n"; //所有顶点都连通,即要求n个点都连通
else{
cout << "NO" << "\n";
}

求连通块个数

畅通工程

刚开始时所有节点的根都为本身,连通块个数为节点个数。

最后,计算有多少个节点的根不再为本身了,改变了一个连通块个数就减一

1
2
3
4
5
6
int cnt = n; //连通块个数
for(int i=1;i<=n;i++){
if(f[i] != i){
cnt --;
}
}

并查集
https://cs-lb.github.io/2024/08/13/algorithm_know/并查集/
作者
Liu Bo
发布于
2024年8月13日
许可协议