C++利用map實(shí)現(xiàn)并查集的方法

這篇文章將為大家詳細(xì)講解有關(guān)C++利用map實(shí)現(xiàn)并查集的方法，小編覺得挺實(shí)用的，因此分享給大家做個(gè)參考，希望大家閱讀完這篇文章后可以有所收獲。

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

利用map實(shí)現(xiàn)主要通過兩個(gè)map的對象 ，一個(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），在找的過程中，會(huì)壓縮路徑，把沿途經(jīng)過的結(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ù)只對代表結(jié)點(diǎn)有效，子結(jié)點(diǎn)無效），主要用處是在合并（union）時(shí)將子結(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)個(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;
};

關(guān)于C++利用map實(shí)現(xiàn)并查集的方法就分享到這里了，希望以上內(nèi)容可以對大家有一定的幫助，可以學(xué)到更多知識。如果覺得文章不錯(cuò)，可以把它分享出去讓更多的人看到。