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.dhdzp.com/article/222108.htm
總結
本篇文章就到這里了，希望能夠給你帶來幫助，也希望您能夠多多關注腳本之家的更多內(nèi)容!
相關文章
虛函數(shù)在 c++ 的繼承體系中是一個非常重要概念，讓我們可以在子類中復寫父類的方法。這篇文章主要介紹了C++ 基礎教程之虛函數(shù)實例代碼的相關資料,需要的朋友可以參考下2020-02-02
C++11運算符重載和向量類重載實例詳解（＜＜,＞＞,+,-,*等）
這篇文章主要給大家介紹了關于C++11運算符重載和向量類重載的相關資料，主要包括＜＜,＞＞,+,-,*等,文中通過示例代碼介紹的非常詳細,需要的朋友可以參考下2021-07-07
本文主要介紹C語言冒泡排序算法,這里給大家舉例說明冒泡排序的思想,并附有代碼示例,有需要的小伙伴可以參考下2016-07-07
這篇文章主要為大家詳細介紹了C語言實現(xiàn)簡易井字棋游戲，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-04-04
人生重開模擬器是前段時間非常火的一個小游戲,所以本文我們將一起學習使用c語言寫一個簡易版的人生重開模擬器,感興趣的小伙伴可以了解下2024-02-02
這篇文章主要介紹了C語言編程中的結構體對齊,值得注意的是一些結構體對齊的例子在不同編譯器下結果可能會不同,需要的朋友可以參考下2016-04-04
這篇文章主要為大家詳細介紹了C++實現(xiàn)簡單24點游戲，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2020-03-03
MD5算法是一種廣泛使用的 Hash 算法,常用于確保信息傳輸?shù)耐暾耘c一致性,本文主要介紹了C/C++實現(xiàn)的MD5哈希校驗的示例代碼,具有一定的參考價值,感興趣的可以了解一下2023-10-10
這篇文章主要為大家詳細介紹了C++如何利用第三方庫實現(xiàn)播放音頻的功能,文中的示例代碼講解詳細,感興趣的小伙伴可以跟隨小編一起學習一下2024-01-01
這篇文章主要給大家介紹了關于C++設計模式之簡單工廠模式的相關資料,簡單工廠模式,主要用于創(chuàng)建對象,添加類時,不會影響以前的系統(tǒng)代碼,需要的朋友可以參考下2021-06-06