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

代码如下：

#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;
};

谢谢阅读，欢迎指出错误！

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持我们。

赞 (0)

相关推荐

  • c++初级并查集知识点总结

    并查集是一种树型的数据结构,用于处理一些不交集的合并及查询问题. 有一个联合- 查找算法定义了两个用于此数据结构的操作: Find :确定元素属于哪一个子集.它可以被用来确定两个元素是否属于同一子集. Union:将两个子集合并成同一个集合. 并查集主要运用在合并元素以及查询两个元素是否在同一集合的问题,在信息学竞赛中广泛涉及 初始化: 一开始,每一个元素都是一个集合,打个比方,每个人所在的 " 家族 " 只有他一个人.我们还需要一个 f 数组,里面存的是他的 "父亲&quo

  • C++实现并查集

    本文实例为大家分享了C++实现并查集的具体代码,供大家参考,具体内容如下 #include <iostream> #include <vector> #include <cassert> using namespace std; class UnionFind{ private: vector<int> parent; int count; //优化,记录p和q所在组的深度,在合并时将深度小的结点的根指向深度大的结点的根 vector<int>

  • C++并查集亲戚(Relations)算法实例

    本文实例讲述了C++并查集亲戚(Relations)算法.分享给大家供大家参考.具体分析如下: 题目: 亲戚(Relations) 或许你并不知道,你的某个朋友是你的亲戚.他可能是你的曾祖父的外公的女婿的外甥的表姐的孙子.如果能得到完整的家谱,判断两个人是否亲戚应该是可行的,但如果两个人的最近公共祖先与他们相隔好几代,使得家谱十分庞大,那么检验亲戚关系实非人力所能及.在这种情况下,最好的帮手就是计算机. 为了将问题简化,你将得到一些亲戚关系的信息,如同Marry和Tom是亲戚,Tom和B en是

  • c++并查集优化（基于size和rank）

    基于size的优化是指:当我们在指定由谁连接谁的时候,size数组维护的是当前集合中元素的个数,让数据少的指向数据多的集合中 基于rank的优化是指:当我们在指定由谁连接谁的时候,rank数组维护的是当前集合中树的高度,让高度低的集合指向高度高的集合 运行时间是差不多的: 基于size的代码: UnionFind3.h #ifndef UNION_FIND3_H_ #define UNION_FIND3_H_ #include<iostream> #include<cassert>

  • C++利用map实现并查集

    并查集(Union-Find)是一种树型的数据结构,用于处理一些不相交集合(Disjoint Sets)的合并及查询问题. 并查集存在两个操作(1.Union 联合 2.finddeputy 查找代表结点) 和一个需要解答的问题( issameset 是否 在一个集合中,或者说是否有同一个代表结点). 利用map实现主要通过两个map的对象 ,一个map<data,data>类型的fathermap,关键字为子结点,值为其父结点(父结点不一定就是代表结点),当我们需要查找两个两个元素是否在一个

  • Java实现快速并查集

    在一些应用的问题中,需将n个不同的元素划分成一组不相交的集合.开始时,每个元素自成一格单元素集合,然后按一定顺序将属于同一组的元素的集合合并.其间要反复用到查询某个元素属于哪个集合的运算.适合于描述这类问题的抽象数据类型称为并查集. 1. 并查集的概述 并查集的数学模型是一组不相交的动态集合的集合S={A,B,C,...},它支持以下的运算: (1)union(A,B):将集合A和B合并,其结果取名为A或B: (2)find(x):找出包含元素x的集合,并返回该集合的名字. 在并查集中需要两个类

  • C语言并查集的非递归实现详解

    目录 [算法分析] [算法代码] 并查集压缩路径非递归写法 参考文章 总结 [算法分析] 经典的递归实现的并查集,在数据规模过大时,可能会爆栈,因此有了并查集的非递归实现.核心代码如下: int find(int x) { int t=x; while(t!=pre[t]) t=pre[t]; while(x!=pre[x]) { x=pre[x]; pre[x]=t; } return t; } void merge(int x,int y) { if(find(x)!=find(y)) pr

  • Java C++题解leetcode886可能的二分法并查集染色法

    目录 题目要求 思路一:反向点+并查集 浅学并查集(Union Find) Java C++ 思路二:染色法 Java C++ 总结 题目要求 思路一:反向点+并查集 根据题意不喜欢就不在一个组可以想到使用并查集,本题是两个集合所以对每一个节点引入一个反向点,使两者分属于不同集合,借此记录前续节点维持的不喜欢关系: 在将每个节点xxx放入组合时,同时将其反向节点x+nx+nx+n放入另一组合,然后向后遍历依次处理每个节点,同时判断相互不喜欢的两个点当前是否会被迫放入一个集合(连通),若是则无法满

  • java编程实现并查集的路径压缩代码详解

    java编程实现并查集的路径压缩代码详解

    首先看两张路径压缩的图片: 并查集(Union-find Sets)是一种非常精巧而实用的数据结构,它主要用于处理一些不相交集合的合并问题.一些常见的用途有求连通子图.求最小生成树的 Kruskal 算法和求最近公共祖先(Least Common Ancestors, LCA)等. 使用并查集时,首先会存在一组不相交的动态集合 S={S 1 ,S 2 ,⋯,S k } ,一般都会使用一个整数表示集合中的一个元素. 每个集合可能包含一个或多个元素,并选出集合中的某个元素作为代表.每个集合中具体包含

  • python实现一个简单的并查集的示例代码

    并查集是一种树型的数据结构,用于处理一些不相交集合的合并及查询问题.常常在使用中以森林来表示. 并查集有三种基本操作,获得根节点,判断两节点是否连通,以及将两不连通的节点相连(相当于将两节点各自的集合合并) 用UnionFind类来表示一个并查集,在构造函数中,初始化一个数组parent,parent[i]表示的含义为,索引为i的节点,它的直接父节点为parent[i].初始化时各个节点都不相连,因此初始化parent[i]=i,让自己成为自己的父节点,从而实现各节点不互连. def __ini

  • c语言数据结构之并查集 总结

    并查集(Union-Find Set): 一种用于管理分组的数据结构.它具备两个操作:(1)查询元素a和元素b是否为同一组 (2) 将元素a和b合并为同一组. 注意:并查集不能将在同一组的元素拆分为两组. 并查集的实现: 用树来实现. 使用树形结构来表示以后,每一组都对应一棵树,然而我们就可以将这个问题转化为树的问题了,我们看两个元素是否为一组我们只要看这两个元素的根是否一致.显然,使用树形结构将问题简单化了.合并时是我们只需要将一组的根与另一组的根相连即可. 并查集的核心在于,一棵树的所有节点

  • 数据结构与算法之并查集(不相交集合)

    认识并查集 对于并查集(不相交集合),很多人会感到很陌生,没听过或者不是特别了解.实际上并查集是一种挺高效的数据结构.实现简单,只是所有元素统一遵从一个规律所以让办事情的效率高效起来. 对于定意义,百科上这么定义的: 并查集,在一些有N个元素的集合应用问题中,我们通常是在开始时让每个元素构成一个单元素的集合,然后按一定顺序将属于同一组的元素所在的集合合并,其间要反复查找一个元素在哪个集合中.其特点是看似并不复杂,但数据量极大,若用正常的数据结构来描述的话,往往在空间上过大,计算机无法承受:即使在

随机推荐