C语言并查集的非递归实现详解 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 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; }