0.题目
1.解析
1.1 并查集
思路
主要三大模板功能 1.初始化(init) 2.寻找父节点(find) 3.合并(merge)
我们在find中可以使用路径压缩简化运算,缩短运行时间
而启发式合并则可以将运行时间压缩,由O(n)到 o(logn)
代码
#include<bits/stdc++.h>
using namespace std;
const int Maxn = 1e6 + 10;
int fa[Maxn+1]; // 记录父节点
int sz[Maxn+1]; // 记录树的大小
int m, n, k;
// 初始化操作
void init(){
for(int i = 1; i <= Maxn; i++){
fa[i] = i;
sz[i] = 1;
}
}
// 寻找父节点(DFS递归)
//int find(int x){
// // 找到根节点
// if(x == fa[x]){
// return x;
// }
// // 没有找到,继续向前DFS递归
// else{
// return find(fa[x]);
// }
//}
// 寻找父节点(路径压缩)
int find(int x){
// 找到根节点
if(x == fa[x]){
return x;
}
// 没有找到,继续向前DFS递归
else{
fa[x] = find(fa[x]);
return fa[x];
}
}
// 合并操作(根节点合并)
//void merge(int x, int y){
// fa[find(x)] = find(y);
//}
void merge(int x,int y)//启发式合并
{
x=find(x);
y=find(y);
if(x!=y)
{
if(sz[x]<sz[y])
swap(x,y);
sz[x]+=sz[y];
fa[y]=x;
}
}
int main(){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n >> m >> k;
init();
for(int i = 0; i < k; i++){
int a, b;
cin >> a >> b;
merge(a, b);
}
int ans = 0;
for(int i = 1; i <= n*m; i++){
if(fa[i] == i){
ans++;
}
}
cout << ans;
return 0;
}
标签:合根,int,查集,蓝桥,init,Maxn,find
From: https://www.cnblogs.com/trmbh12/p/18131686