【算法分析】
经典的递归实现的并查集,在数据规模过大时,可能会爆栈,因此有了并查集的非递归实现。核心代码如下:
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