亚洲乱码中文字幕综合,中国熟女仑乱hd,亚洲精品乱拍国产一区二区三区,一本大道卡一卡二卡三乱码全集资源,又粗又黄又硬又爽的免费视频

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

 更新時(shí)間:2020年07月05日 14:33:12   作者:y1054765649  
這篇文章主要為大家詳細(xì)介紹了C++利用map實(shí)現(xiàn)并查集,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下

并查集(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的對(duì)象 ,一個(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ù)只對(duì)代表結(jié)點(diǎn)有效,子結(jié)點(diǎn)無效),主要用處是在合并(union)時(shí)將子結(jié)點(diǎn)較少的代表結(jié)點(diǎn)掛在子結(jié)點(diǎn)代表較多的代表結(jié)點(diǎn)下,且sizemap中父結(jié)點(diǎn)對(duì)應(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;
};

謝謝閱讀,歡迎指出錯(cuò)誤!

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

相關(guān)文章

  • C++之openFrameworks框架介紹

    C++之openFrameworks框架介紹

    本章我們將介紹一個(gè)非常好用的跨平臺(tái)的 C++開源框架 openFrameworks。它是一個(gè)開源的跨平臺(tái)的C++工具包,方便開發(fā)者創(chuàng)建出一個(gè)更簡(jiǎn)單和直觀的框架,擅長(zhǎng)開發(fā)圖像和動(dòng)畫,感興趣的同學(xué)可以參考一下
    2023-05-05
  • TypeScript的函數(shù)定義與使用案例教程

    TypeScript的函數(shù)定義與使用案例教程

    這篇文章主要介紹了TypeScript的函數(shù)定義與使用案例教程,本篇文章通過簡(jiǎn)要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下
    2021-07-07
  • C++基于Floyd算法實(shí)現(xiàn)校園導(dǎo)航系統(tǒng)

    C++基于Floyd算法實(shí)現(xiàn)校園導(dǎo)航系統(tǒng)

    這篇文章主要為大家詳細(xì)介紹了C++基于Floyd算法實(shí)現(xiàn)校園導(dǎo)航系統(tǒng),文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下
    2022-03-03
  • 手動(dòng)添加bits/stdc++.h到vs2017的詳細(xì)步驟

    手動(dòng)添加bits/stdc++.h到vs2017的詳細(xì)步驟

    這篇文章主要介紹了手動(dòng)添加bits/stdc++.h到vs2017的詳細(xì)步驟,本文給大家介紹的非常詳細(xì),具有一定的參考借鑒價(jià)值,需要的朋友可以參考下
    2020-02-02
  • OpenCV實(shí)現(xiàn)特征檢測(cè)和特征匹配方法匯總

    OpenCV實(shí)現(xiàn)特征檢測(cè)和特征匹配方法匯總

    一幅圖像中總存在著其獨(dú)特的像素點(diǎn),這些點(diǎn)我們可以認(rèn)為就是這幅圖像的特征,成為特征點(diǎn),本文主要介紹了OpenCV實(shí)現(xiàn)特征檢測(cè)和特征匹配方法,感興趣的可以了解一下
    2021-08-08
  • C++的智能指針你真的了解嗎

    C++的智能指針你真的了解嗎

    這篇文章主要為大家詳細(xì)介紹了C++的智能指針,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下,希望能夠給你帶來幫助
    2022-03-03
  • C語言程序的編譯與預(yù)處理基礎(chǔ)定義講解

    C語言程序的編譯與預(yù)處理基礎(chǔ)定義講解

    在ANSI C的任意一種實(shí)現(xiàn)中,存在2中不同的環(huán)境。第一種是翻譯環(huán)境,負(fù)責(zé)將源代碼轉(zhuǎn)換成可執(zhí)行的機(jī)器指令;第二種是執(zhí)行環(huán)境,用于實(shí)際執(zhí)行代碼。一個(gè)程序從源代碼到可執(zhí)行程序一共會(huì)經(jīng)歷四個(gè)過程,分別是預(yù)處理、編譯、匯編、鏈接,本篇讓我們來了解編譯與預(yù)處理
    2022-04-04
  • C++詳細(xì)講解print緩沖區(qū)的刷新

    C++詳細(xì)講解print緩沖區(qū)的刷新

    這篇文章主要介紹了print緩沖區(qū)刷新問題,實(shí)現(xiàn)代碼簡(jiǎn)單易懂,具有很好的參考價(jià)值,希望對(duì)大家有所幫助,需要的朋友可以參考下
    2022-05-05
  • C語言自定義數(shù)據(jù)類型的結(jié)構(gòu)體、枚舉和聯(lián)合詳解

    C語言自定義數(shù)據(jù)類型的結(jié)構(gòu)體、枚舉和聯(lián)合詳解

    這篇文章主要給大家介紹了關(guān)于C語言自定義數(shù)據(jù)類型的結(jié)構(gòu)體、枚舉和聯(lián)合的相關(guān)資料,文中通過示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧
    2021-05-05
  • 解決codeblocks斷點(diǎn)不停無效的問題

    解決codeblocks斷點(diǎn)不停無效的問題

    今天小編就為大家分享一篇解決codeblocks斷點(diǎn)不停無效的問題,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。一起跟隨小編過來看看吧
    2019-12-12

最新評(píng)論