C++利用map实现并查集

  • 更新时间:2023-01-09 09:18:39
  • 编辑:郑珺娅

并查集(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/C++实现控制台输出不同颜色字体的实例讲解

    这篇文章主要介绍了C/C++实现控制台输出不同颜色字体的方法,涉及C++控制台文字属性相关设置操作技巧,需要的朋友可以参考下

    发布时间:2021-05-30

  • C++树之遍历二叉树实例详解

    这篇文章主要给大家介绍了关于C++树之遍历二叉树的相关资料,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧

    发布时间:2022-04-11

  • 一篇文章带你了解C++特殊类的设计

    这篇文章主要为大家详细介绍了C++特殊类的设计,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下,希望能够给你带来帮助

    发布时间:2022-04-04

  • C++子类父类成员函数的覆盖和隐藏实例详解

    C++子类父类成员函数的覆盖和隐藏实例详解

    给大家整理一篇关于C++的教程,这篇文章主要介绍了C++子类父类成员函数的覆盖和隐藏实例详解的相关资料,需要的朋友可以参考下

    发布时间:2022-09-12

  • C,C++中常用的操作字符串的函数

    为网友们分享了关于C++的教程,这篇文章主要介绍了C,C++中常用的操作字符串的函数,需要的朋友可以参考下

    发布时间:2022-10-10

  • C++实现归并排序的实例

    这篇文章主要为大家详细介绍了C++实现归并排序,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下

    发布时间:2021-10-08

  • C++实现教师管理系统

    这篇文章主要为大家详细介绍了C++实现教师管理系统,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下

    发布时间:2022-04-16

用户留言