c语言典型递归问题（先序遍历的非递归算法c语言）

目录

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

【算法分析】

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

?

1 2 3 4 5 6 7 8 9 10 11 12

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 利用非递归实现的并查集的代码如下：

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39

#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:
2
5 3
1 2
2 3
4 5
5 1
2 5
out:
2
4
*/

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

?

1 2 3 4 5 6 7 8 9 10

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

参考文章

http://www.zzvips.com/article/216831.html

总结

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

原文链接：https://blog.csdn.net/hnjzsyjyj/article/details/120143770