常规并查集
模板
#define Maxsize 100+1
int f[Maxsize];
void init(int n){
for(int i = 1; i <= n; i++)
f[i] = i;
}
int find_f(int a){
if(f[a] == a){
return a;
}else{
return f[a] = find_f(f[a]);
}
}
void union_f(int a,int b){
int af = find_f(a);
int bf = find_f(b);
f[bf] = af;
}
bool same_f(int a,int b){
return find_f(a) == find_f(b);
}
按秩合并
可以提高效率,减少路径压缩
#define Maxsize 100+1
int f[Maxsize];
int r[Maxsize];
void init(int n){
for(int i = 1; i <= n; i++){
f[i] = i;
r[i] = 0;
}
}
int find_f(int a){
if(f[a] == a){
return a;
}else{
return f[a] = find_f(f[a]);
}
}
int union_f(int a,int b){
int af = find_f(a);
int bf = find_f(b);
if(r[af] > r[bf]){
f[bf] = af;
}else if(r[af] < r[bf]){
f[af] = bf;
}else{
f[bf] = af;
r[af]++;
}
}
int same_f(int a,int b){
return find_f(a) == find_f(b);
}
原文链接: https://www.cnblogs.com/popodynasty/p/13320679.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍;
也有高质量的技术群,里面有嵌入式、搜广推等BAT大佬
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/366971
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!