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