創(chuàng)新互聯(lián)www.cdcxhl.cn八線動態(tài)BGP香港云服務器提供商，新人活動買多久送多久，劃算不套路！

十年的黑河網(wǎng)站建設經(jīng)驗，針對設計、前端、開發(fā)、售后、文案、推廣等六對一服務，響應快，48小時及時工作處理。成都營銷網(wǎng)站建設的優(yōu)勢是能夠根據(jù)用戶設備顯示端的尺寸不同，自動調(diào)整黑河建站的顯示方式，使網(wǎng)站能夠適用不同顯示終端，在瀏覽器中調(diào)整網(wǎng)站的寬度，無論在任何一種瀏覽器上瀏覽網(wǎng)站，都能展現(xiàn)優(yōu)雅布局與設計，從而大程度地提升瀏覽體驗。創(chuàng)新互聯(lián)從事“黑河網(wǎng)站設計”,“黑河網(wǎng)站推廣”以來，每個客戶項目都認真落實執(zhí)行。

這篇文章將為大家詳細講解有關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，關鍵字為子結(jié)點，值為其父結(jié)點（父結(jié)點不一定就是代表結(jié)點），當我們需要查找兩個兩個元素是否在一個集合中時，只需一直向上找（函數(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é)點對應的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;
};

本文名稱：C++利用map實現(xiàn)并查集的方法-創(chuàng)新互聯(lián)
文章地址：http://chinadenli.net/article46/dspihg.html

成都網(wǎng)站建設公司_創(chuàng)新互聯(lián)，為您提供面包屑導航、用戶體驗、ChatGPT、定制開發(fā)、網(wǎng)站排名、App設計

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)