C++利用map實現(xiàn)并查集

更新時間：2020年07月05日 14:33:12 作者：y1054765649

這篇文章主要為大家詳細(xì)介紹了C++利用map實現(xiàn)并查集，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下

并查集（Union-Find）是一種樹型的數(shù)據(jù)結(jié)構(gòu)，用于處理一些不相交集合（Disjoint Sets）的合并及查詢問題。并查集存在兩個操作（1.Union 聯(lián)合 2.finddeputy 查找代表結(jié)點(diǎn)）和一個需要解答的問題（ issameset 是否在一個集合中，或者說是否有同一個代表結(jié)點(diǎn)）。

利用map實現(xiàn)主要通過兩個map的對象，一個map<data,data>類型的fathermap，關(guān)鍵字為子結(jié)點(diǎn)，值為其父結(jié)點(diǎn)（父結(jié)點(diǎn)不一定就是代表結(jié)點(diǎn)），當(dāng)我們需要查找兩個兩個元素是否在一個集合中時，只需一直向上找（函數(shù)finddupty），在找的過程中，會壓縮路徑，把沿途經(jīng)過的結(jié)點(diǎn)直接掛在其代表結(jié)點(diǎn)下，看是否有共同的代表結(jié)點(diǎn)；

一個map<data,int>類型的sizemap，key為結(jié)點(diǎn)，value為其子結(jié)點(diǎn)的個數(shù)（這個個數(shù)只對代表結(jié)點(diǎn)有效，子結(jié)點(diǎn)無效），主要用處是在合并（union）時將子結(jié)點(diǎn)較少的代表結(jié)點(diǎn)掛在子結(jié)點(diǎn)代表較多的代表結(jié)點(diǎn)下，且sizemap中父結(jié)點(diǎn)對應(yīng)的value要加上子結(jié)點(diǎn)較少的代表的結(jié)點(diǎn)個數(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;
};

謝謝閱讀，歡迎指出錯誤！

以上就是本文的全部內(nèi)容，希望對大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。

您可能感興趣的文章: