目录【算法分析】【算法代码】并查集压缩路径非递归写法参考文章总结【算法分析】 经典的递归实现的并查集,在数据规模过大时,可能会爆栈,因此有了并查集的非递归实现。核心代码如下: i
经典的递归实现的并查集,在数据规模过大时,可能会爆栈,因此有了并查集的非递归实现。核心代码如下:
int find(int x) {
int t=x;
while(t!=pre[t]) t=pre[t];
while(x!=pre[x]) {
x=pre[x];
pre[x]=t;
}
return t;
}
void merge(int x,int y) {
if(find(x)!=find(y)) pre[find(x)]=find(y);
}
对问题 Http://acm.hdu.edu.cn/showproblem.PHP?pid=1213 利用非递归实现的并查集的代码如下:
#include <iOStream>
using namespace std;
const int maxn=1005;
int pre[maxn];
//int find(int x) {
// if(x!=pre[x]) pre[x]=find(pre[x]);
// return pre[x];
//}
int find(int x) {
int t=x;
while(t!=pre[t]) t=pre[t];
while(x!=pre[x]) {
x=pre[x];
pre[x]=t;
}
return t;
}
void merge(int x,int y) {
if(find(x)!=find(y)) pre[find(x)]=find(y);
}
int main() {
int T,N,M;
int p,q;
scanf("%d",&T);
while(T--) {
int ans=0;
scanf("%d%d",&N,&M);
for(int i=1; i<=N; i++) pre[i]=i;
for(int i=1; i<=M; i++) {
scanf("%d%d",&p,&q);
merge(p,q);
}
for(int i=1; i<=N; i++) {
if(find(i)==i) ans++;
}
printf("%d\n",ans);
}
return 0;
}
int find(int x){
int temp=x;
while(temp!=d[temp])
temp=d[temp];
while(x!=d[x]){
x=d[x];
d[x]=temp;
}
return temp;
}
//www.jb51.net/article/222108.htm
本篇文章就到这里了,希望能够给你带来帮助,也希望您能够多多关注编程网的更多内容!
--结束END--
本文标题: C语言并查集的非递归实现详解
本文链接: https://www.lsjlt.com/news/134881.html(转载时请注明来源链接)
有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341
下载Word文档到电脑,方便收藏和打印~
2024-03-01
2024-03-01
2024-02-29
2024-02-29
2024-02-29
2024-02-29
2024-02-29
2024-02-29
2024-02-29
2024-02-29
回答
回答
回答
回答
回答
回答
回答
回答
回答
回答
0