C++利用map實現(xiàn)并查集
并查集（Union-Find）是一種樹型的數(shù)據(jù)結(jié)構(gòu)，用于處理一些不相交集合（Disjoint Sets）的合并及查詢問題。 并查集存在兩個操作（1.Union 聯(lián)合 2.finddeputy 查找代表結(jié)點） 和一個需要解答的問題（ issameset 是否 在一個集合中，或者說是否有同一個代表結(jié)點）。
利用map實現(xiàn)主要通過兩個map的對象 ，一個map<data,data>類型的fathermap，關(guān)鍵字為子結(jié)點，值為其父結(jié)點（父結(jié)點不一定就是代表結(jié)點），當(dāng)我們需要查找兩個兩個元素是否在一個集合中時，只需一直向上找（函數(shù)finddupty），在找的過程中，會壓縮路徑，把沿途經(jīng)過的結(jié)點直接掛在其代表結(jié)點下，看是否有共同的代表結(jié)點；
一個map<data,int>類型的sizemap，key為結(jié)點，value為其子結(jié)點的個數(shù)（這個個數(shù)只對代表結(jié)點有效，子結(jié)點無效），主要用處是在合并（union）時將子結(jié)點較少的代表結(jié)點掛在子結(jié)點代表較多的代表結(jié)點下，且sizemap中父結(jié)點對應(yīng)的value要加上子結(jié)點較少的代表的結(jié)點個數(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é)點，且路徑壓縮
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;
};
謝謝閱讀，歡迎指出錯誤！
以上就是本文的全部內(nèi)容，希望對大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。
相關(guān)文章
本章我們將介紹一個非常好用的跨平臺的 C++開源框架 openFrameworks。它是一個開源的跨平臺的C++工具包，方便開發(fā)者創(chuàng)建出一個更簡單和直觀的框架，擅長開發(fā)圖像和動畫，感興趣的同學(xué)可以參考一下2023-05-05
這篇文章主要介紹了TypeScript的函數(shù)定義與使用案例教程,本篇文章通過簡要的案例,講解了該項技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下2021-07-07
C++基于Floyd算法實現(xiàn)校園導(dǎo)航系統(tǒng)
這篇文章主要為大家詳細(xì)介紹了C++基于Floyd算法實現(xiàn)校園導(dǎo)航系統(tǒng)，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-03-03
手動添加bits/stdc++.h到vs2017的詳細(xì)步驟
這篇文章主要介紹了手動添加bits/stdc++.h到vs2017的詳細(xì)步驟，本文給大家介紹的非常詳細(xì)，具有一定的參考借鑒價值,需要的朋友可以參考下2020-02-02
一幅圖像中總存在著其獨特的像素點，這些點我們可以認(rèn)為就是這幅圖像的特征，成為特征點，本文主要介紹了OpenCV實現(xiàn)特征檢測和特征匹配方法，感興趣的可以了解一下2021-08-08
這篇文章主要為大家詳細(xì)介紹了C++的智能指針，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助2022-03-03
在ANSI C的任意一種實現(xiàn)中，存在2中不同的環(huán)境。第一種是翻譯環(huán)境，負(fù)責(zé)將源代碼轉(zhuǎn)換成可執(zhí)行的機器指令；第二種是執(zhí)行環(huán)境，用于實際執(zhí)行代碼。一個程序從源代碼到可執(zhí)行程序一共會經(jīng)歷四個過程，分別是預(yù)處理、編譯、匯編、鏈接，本篇讓我們來了解編譯與預(yù)處理2022-04-04
這篇文章主要介紹了print緩沖區(qū)刷新問題，實現(xiàn)代碼簡單易懂，具有很好的參考價值，希望對大家有所幫助，需要的朋友可以參考下2022-05-05
C語言自定義數(shù)據(jù)類型的結(jié)構(gòu)體、枚舉和聯(lián)合詳解
這篇文章主要給大家介紹了關(guān)于C語言自定義數(shù)據(jù)類型的結(jié)構(gòu)體、枚舉和聯(lián)合的相關(guān)資料，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2021-05-05
今天小編就為大家分享一篇解決codeblocks斷點不停無效的問題，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2019-12-12