欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

C語言并查集的非遞歸實現(xiàn)詳解

 更新時間：2021年09月07日 11:30:28   作者：hnjzsyjyj  
以下是對C語言并查集的遞歸實現(xiàn)與非遞歸實現(xiàn)代碼進行了詳細的介紹，需要的朋友可以過來參考下，希望能夠給你帶來幫助

【算法分析】

經(jīng)典的遞歸實現(xiàn)的并查集，在數(shù)據(jù)規(guī)模過大時，可能會爆棧，因此有了并查集的非遞歸實現(xiàn)。核心代碼如下：

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 利用非遞歸實現(xiàn)的并查集的代碼如下：

#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
*/

并查集壓縮路徑非遞歸寫法

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.dbjr.com.cn/article/222108.htm

總結(jié)

本篇文章就到這里了，希望能夠給你帶來幫助，也希望您能夠多多關(guān)注腳本之家的更多內(nèi)容!

相關(guān)文章

最新評論