創(chuàng)新互聯(lián)www.cdcxhl.cn八線動(dòng)態(tài)BGP香港云服務(wù)器提供商,新人活動(dòng)買多久送多久,劃算不套路!
十年的黑河網(wǎng)站建設(shè)經(jīng)驗(yàn),針對(duì)設(shè)計(jì)、前端、開(kāi)發(fā)、售后、文案、推廣等六對(duì)一服務(wù),響應(yīng)快,48小時(shí)及時(shí)工作處理。成都營(yíng)銷網(wǎng)站建設(shè)的優(yōu)勢(shì)是能夠根據(jù)用戶設(shè)備顯示端的尺寸不同,自動(dòng)調(diào)整黑河建站的顯示方式,使網(wǎng)站能夠適用不同顯示終端,在瀏覽器中調(diào)整網(wǎng)站的寬度,無(wú)論在任何一種瀏覽器上瀏覽網(wǎng)站,都能展現(xiàn)優(yōu)雅布局與設(shè)計(jì),從而大程度地提升瀏覽體驗(yàn)。創(chuàng)新互聯(lián)從事“黑河網(wǎng)站設(shè)計(jì)”,“黑河網(wǎng)站推廣”以來(lái),每個(gè)客戶項(xiàng)目都認(rèn)真落實(shí)執(zhí)行。這篇文章將為大家詳細(xì)講解有關(guān)C++利用map實(shí)現(xiàn)并查集的方法,小編覺(jué)得挺實(shí)用的,因此分享給大家做個(gè)參考,希望大家閱讀完這篇文章后可以有所收獲。
并查集(Union-Find)是一種樹(shù)型的數(shù)據(jù)結(jié)構(gòu),用于處理一些不相交集合(Disjoint Sets)的合并及查詢問(wèn)題。 并查集存在兩個(gè)操作(1.Union 聯(lián)合 2.finddeputy 查找代表結(jié)點(diǎn)) 和一個(gè)需要解答的問(wèn)題( issameset 是否 在一個(gè)集合中,或者說(shuō)是否有同一個(gè)代表結(jié)點(diǎn))。
利用map實(shí)現(xiàn)主要通過(guò)兩個(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),在找的過(guò)程中,會(huì)壓縮路徑,把沿途經(jīng)過(guò)的結(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)無(wú)效),主要用處是在合并(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; };
本文名稱:C++利用map實(shí)現(xiàn)并查集的方法-創(chuàng)新互聯(lián)
文章地址:http://m.rwnh.cn/article46/dspihg.html
成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián),為您提供面包屑導(dǎo)航、用戶體驗(yàn)、ChatGPT、定制開(kāi)發(fā)、網(wǎng)站排名、App設(shè)計(jì)
聲明:本網(wǎng)站發(fā)布的內(nèi)容(圖片、視頻和文字)以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主,如果涉及侵權(quán)請(qǐng)盡快告知,我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng),如需處理請(qǐng)聯(lián)系客服。電話:028-86922220;郵箱:631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載,或轉(zhuǎn)載時(shí)需注明來(lái)源: 創(chuàng)新互聯(lián)
猜你還喜歡下面的內(nèi)容