服务器之家:专注于服务器技术及软件下载分享
分类导航

PHP教程|ASP.NET教程|Java教程|ASP教程|编程技术|正则表达式|C/C++|IOS|C#|Swift|Android|VB|R语言|JavaScript|易语言|vb.net|

服务器之家 - 编程语言 - C/C++ - C++利用map实现并查集

C++利用map实现并查集

2021-09-14 15:05y1054765649 C/C++

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

并查集(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要加上子结点较少的代表的结点个数。

代码如下:

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#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;
};

谢谢阅读,欢迎指出错误!

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持服务器之家。

原文链接:https://blog.csdn.net/y1054765649/article/details/88675276

延伸 · 阅读

精彩推荐