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