C++利用map實(shí)現(xiàn)并查集
并查集(Union-Find)是一種樹型的數(shù)據(jù)結(jié)構(gòu),用于處理一些不相交集合(Disjoint Sets)的合并及查詢問題。 并查集存在兩個(gè)操作(1.Union 聯(lián)合 2.finddeputy 查找代表結(jié)點(diǎn)) 和一個(gè)需要解答的問題( issameset 是否 在一個(gè)集合中,或者說是否有同一個(gè)代表結(jié)點(diǎn))。
利用map實(shí)現(xiàn)主要通過兩個(gè)map的對(duì)象 ,一個(gè)map<data,data>類型的fathermap,關(guān)鍵字為子結(jié)點(diǎn),值為其父結(jié)點(diǎn)(父結(jié)點(diǎn)不一定就是代表結(jié)點(diǎn)),當(dāng)我們需要查找兩個(gè)兩個(gè)元素是否在一個(gè)集合中時(shí),只需一直向上找(函數(shù)finddupty),在找的過程中,會(huì)壓縮路徑,把沿途經(jīng)過的結(jié)點(diǎn)直接掛在其代表結(jié)點(diǎn)下,看是否有共同的代表結(jié)點(diǎn);
一個(gè)map<data,int>類型的sizemap,key為結(jié)點(diǎn),value為其子結(jié)點(diǎn)的個(gè)數(shù)(這個(gè)個(gè)數(shù)只對(duì)代表結(jié)點(diǎn)有效,子結(jié)點(diǎn)無效),主要用處是在合并(union)時(shí)將子結(jié)點(diǎn)較少的代表結(jié)點(diǎn)掛在子結(jié)點(diǎn)代表較多的代表結(jié)點(diǎn)下,且sizemap中父結(jié)點(diǎn)對(duì)應(yīng)的value要加上子結(jié)點(diǎn)較少的代表的結(jié)點(diǎn)個(gè)數(shù)。
代碼如下:
#include<map> #include<list> #include<iostream> using namespace std; template<typename data> class Unionfindset{ public: void makesets(list<data> nodes) { fathermap.clear(); sizemap.clear(); for(auto node:nodes) { fathermap[node]=node; sizemap[node]=1; } } //尋找代表結(jié)點(diǎn),且路徑壓縮 data findduputy(data node) { data father=fathermap[node]; if(father!=node) { return findduputy(father); } fathermap[node]=father; return father; } void Union(data a ,data b) { data ahead=findduputy(a); data bhead=findduputy(b); if(ahead!=bhead) { data asize=sizemap[a]; data bsize=sizemap[b]; if(asize<bsize) { fathermap[a]=b; sizemap[b]=bsize+asize; } else { fathermap[b]=a; sizemap[a]=bsize+asize; } } } bool issameset(data a,data b) { return findduputy(a)==findduputy(b); } private: map<data,data> fathermap; map<data,data> sizemap; };
謝謝閱讀,歡迎指出錯(cuò)誤!
以上就是本文的全部?jī)?nèi)容,希望對(duì)大家的學(xué)習(xí)有所幫助,也希望大家多多支持腳本之家。
相關(guān)文章
C++基于Floyd算法實(shí)現(xiàn)校園導(dǎo)航系統(tǒng)
這篇文章主要為大家詳細(xì)介紹了C++基于Floyd算法實(shí)現(xiàn)校園導(dǎo)航系統(tǒng),文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2022-03-03手動(dòng)添加bits/stdc++.h到vs2017的詳細(xì)步驟
這篇文章主要介紹了手動(dòng)添加bits/stdc++.h到vs2017的詳細(xì)步驟,本文給大家介紹的非常詳細(xì),具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2020-02-02OpenCV實(shí)現(xiàn)特征檢測(cè)和特征匹配方法匯總
一幅圖像中總存在著其獨(dú)特的像素點(diǎn),這些點(diǎn)我們可以認(rèn)為就是這幅圖像的特征,成為特征點(diǎn),本文主要介紹了OpenCV實(shí)現(xiàn)特征檢測(cè)和特征匹配方法,感興趣的可以了解一下2021-08-08C語言自定義數(shù)據(jù)類型的結(jié)構(gòu)體、枚舉和聯(lián)合詳解
這篇文章主要給大家介紹了關(guān)于C語言自定義數(shù)據(jù)類型的結(jié)構(gòu)體、枚舉和聯(lián)合的相關(guān)資料,文中通過示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2021-05-05