C语言并查集的非递归实现详解

目录【算法分析】【算法代码】并查集压缩路径非递归写法参考文章总结

【算法分析】

经典的递归实现的并查集，在数据规模过大时，可能会爆栈，因此有了并查集的非递归实现。核心代码如下：

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;}

/*in:25 31 22 34 55 12 5out:24*/

并查集压缩路径非递归写法

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

总结

本篇文章就到这里了，希望能够给你带来帮助，也希望您能够多多关注的更多内容!

青春气贯长虹，勇敢盖过怯懦，进取压倒苟安。