溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
這篇文章將為大家詳細講解有關C++利用map實現并查集的方法，小編覺得挺實用的，因此分享給大家做個參考，希望大家閱讀完這篇文章后可以有所收獲。
并查集（Union-Find）是一種樹型的數據結構，用于處理一些不相交集合（Disjoint Sets）的合并及查詢問題。 并查集存在兩個操作（1.Union 聯合 2.finddeputy 查找代表結點） 和一個需要解答的問題（ issameset 是否 在一個集合中，或者說是否有同一個代表結點）。
利用map實現主要通過兩個map的對象 ，一個map<data,data>類型的fathermap，關鍵字為子結點，值為其父結點（父結點不一定就是代表結點），當我們需要查找兩個兩個元素是否在一個集合中時，只需一直向上找（函數finddupty），在找的過程中，會壓縮路徑，把沿途經過的結點直接掛在其代表結點下，看是否有共同的代表結點；
一個map<data,int>類型的sizemap，key為結點，value為其子結點的個數（這個個數只對代表結點有效，子結點無效），主要用處是在合并（union）時將子結點較少的代表結點掛在子結點代表較多的代表結點下，且sizemap中父結點對應的value要加上子結點較少的代表的結點個數。
代碼如下：
#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++利用map實現并查集的方法就分享到這里了，希望以上內容可以對大家有一定的幫助，可以學到更多知識。如果覺得文章不錯，可以把它分享出去讓更多的人看到。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
