C++并查集常用操作

并查集 是一种树型的数据结构,用于处理一些不相加集合的合并和查询问题。在使用中常常以森林来表示。 并查集也是用来维护集合的,和前面学习的set不同之处在于,并查集能很方便地同时维护很多集合。如果用set来维护会非常的麻烦。并查集的核心思想是记录每个结点的父亲结点是哪个结点。

前言

并查集是一种多叉树，用于处理不相交的集合的合并与查询问题（判断）。

通俗理解：在日常生活中，我们会因为某个人是自己的朋友，哪怕是朋友的朋友也是有朋友，会给予通融、 偏袒。而并查集的基本概念，就是判断某两个集合是否是“朋友”关系，并让两个集合成为“朋友”

常用操作

初始化：每个结点单独作为一个集合

查询：求元素所在的集合的代表元素，即根结点

合并：将两个元素所在的集合，合并为一个集合

合并之前，应先判断两个元素是否属于同一集合，用上面的“查询”来实现

算法实现

初始化:初始的时候每个结点各自为一个集合,father[i]表示结点 i 的父亲结点,如果 father[i]=i,我们认为这个结点是当前集合根结点（开始时每个节点根节点是他自己）。

void init() {

    for (int i = 1; i <= n; ++i) {

        father[i] = i;

    }

}

查找:查找结点所在集合的根结点,结点 x 的根结点必然也是其父亲结点的根结点（像是有递归的样子）。

int get(int x) {

    if (father[x] == x) { // x 结点就是根结点

        return x; 

    }

    return get(father[x]); // 如果该节点不是根节点，继续寻找父结点的根结点

}

合并:将两个元素所在的集合合并在一起,通常来说,合并之前先判断两个元素是否属于同一集合。

void hebing(int x, int y) {

    x = find(x);

    y = find(y);

    if (x != y) { // 不在同一个集合

        father[y] = x;//将根节点合并

    }

}

上面三个操作是并查集常用的操作

前面的并查集的复杂度实际上在有些极端情况会很慢。比如树的结构正好是一条链，那么最坏情况下，每次查询的复杂度达到了O(n) 。这并不是我们期望的结果。路径压缩的思想是，我们只关心每个结点的父结点，而并不太关心树的真正的结构（递归查找相当浪费时间）如下：

当想去访问6的根节点时，要访问5的根节点，想去访问5的根节点，又要去访问4的根节点..........以此类推，此时并查集退化为线性。

这样我们在一次查询的时候，可以把查询路径上的所有结点的father[i]都赋值成为根结点。只需要在我们之前的查询函数上面进行很小的改动

int findf(int k)
{     if(f[k] == k)
        return k;
        return f[k] = findf(f[k]); //后来更新的点的根节点直接为最开始的点，一步找到总根节点。
}

初步学习理解，如有不足请指出，谢谢

到此这篇关于C++并查集基础的文章就介绍到这了,更多相关C++并查集内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

赞 (0)

相关推荐

  • C++实现并查集

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

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

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

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

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

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

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

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

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

  • C++并查集常用操作

    C++并查集常用操作

    并查集 是一种树型的数据结构,用于处理一些不相加集合的合并和查询问题.在使用中常常以森林来表示. 并查集也是用来维护集合的,和前面学习的set不同之处在于,并查集能很方便地同时维护很多集合.如果用set来维护会非常的麻烦.并查集的核心思想是记录每个结点的父亲结点是哪个结点. 前言 并查集是一种多叉树,用于处理不相交的集合的合并与查询问题(判断). 通俗理解:在日常生活中,我们会因为某个人是自己的朋友,哪怕是朋友的朋友也是有朋友,会给予通融. 偏袒.而并查集的基本概念,就是判断某两个集合是否是"朋

  • java 数据结构并查集详解

    java 数据结构并查集详解

    目录 一.概述 二.实现 2.1 Quick Find实现 2.2 Quick Union实现 三.优化 3.1基于size的优化 3.2基于rank优化 3.2.1路径压缩(Path Compression ) 3.2.2路径分裂(Path Spliting) 3.2.3路径减半(Path Halving) 一.概述 并查集:一种树型数据结构,用于解决一些不相交集合的合并及查询问题.例如:有n个村庄,查询2个村庄之间是否有连接的路,连接2个村庄 两大核心: 查找 (Find) : 查找元素所在

  • Spring Boot整合mybatis使用注解实现动态Sql、参数传递等常用操作(实现方法)

    前面介绍了Spring Boot 整合mybatis 使用注解的方式实现数据库操作,介绍了如何自动生成注解版的mapper 和pojo类. 接下来介绍使用mybatis 常用注解以及如何传参数等数据库操作中的常用操作. 其实,mybatis 注解方式 和 XML配置方式两者的使用基本上相同,只有在构建 SQL 脚本有所区别,所以这里重点介绍两者之间的差异,以及增删改查,参数传递等注解的常用操作. 详解SpringBoot 快速整合Mybatis(去XML化+注解进阶)已经介绍过了,不清楚的朋友可

  • MySQL条件查询语句常用操作全面汇总

    MySQL条件查询语句常用操作全面汇总

    目录 模糊查询 union 排序 数量限制 分组 综合 顾名思义, 条件查询就是使用where字句 , 将满足条件的数据筛选出来 语法 : select < 结果 > from < 表名 > where < 条件 > 这里我们以t_user表为例 -- 查询性别为男的信息 SELECT * FROM t_user WHERE sex='男' -- 查询性别不为男的信息 SELECT * FROM t_user WHERE NOT sex='男' -- 查询性别为男并且年

  • 浅谈python中列表、字符串、字典的常用操作

    列表操作如此下: a = ["haha","xixi","baba"] 增:a.append[gg] a.insert[1,gg] 在下标为1的地方,新增 gg 删:a.remove(haha) 删除列表中从左往右,第一个匹配到的 haha del a.[0] 删除下标为0 对应的值 a.pop(0) 括号里不写内容,默认删除最后一个,写了,就删除对应下标的内容 改:a.[0] = "gg" 查:a[0] a.index(&q

  • php中的mongodb select常用操作代码示例

    前面说到了mongodb安装,配置,集群,以及php的插入与更新等,请参考:mongodb. 下面说一下,mongodb select的常用操作 测试数据: 复制代码 代码如下: { "_id" : 1, "title" : "红楼梦", "auther" : "曹雪芹", "typeColumn" : "test", "money" : 80,

  • 浅谈MySQL在cmd和python下的常用操作

    环境配置1:安装mysql,环境变量添加mysql的bin目录 环境配置2:python安装MySQL-Python 请根据自身操作系统下载安装,否则会报c ++ compile 9.0,import _mysql等错误 windows10 64位操作系统可到 http://www.lfd.uci.edu/~gohlke/pythonlibs/ 下载安装MySQL-Python包,至于whl和tar.gz在windows和Linux下的安装方法可查看我的上一篇文章 一 .cmd命令下的操作: 连

  • 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

随机推荐