[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:
2
5 3
1 2
2 3
4 5

5 1
2 5

out:
2
4
*/

【参考文献】
https://www.cnblogs.com/war1111/p/12526682.html
https://blog.csdn.net/hnjzsyjyj/article/details/120142775