并查集及其简单应用

在这里插入图片描述

文章目录

  • 一.并查集
  • 二.并查集的实现
  • 三.并查集的基本应用

一.并查集

  • 并查集的逻辑结构:由多颗不相连通多叉树构成的森林(一个这样的多叉树就是森林的一个连通分量)

    • 并查集的元素(树节点)用0~9的整数表示,并查集可以表示如下: 在这里插入图片描述
  • 并查集的物理存储结构:并查集一般采用顺序结构实现,用数组下标表示并查集的元素,数组元素用于记录并查集中的元素间的关系:在这里插入图片描述

    • 并查集的元素对应的数组元素负数,则表示该并查集元素某颗多叉树的根且没有前驱结点,负数的绝对值表示该颗多叉树(并查集的连通分量)的元素个数
    • 并查集的元素对应的数组元素非负数,这个非负数则表示该并查集的元素的前驱结点
  • 并查集数据结构常用的运算就是==(连通分量)多叉树间的合并算法==:在这里插入图片描述

二.并查集的实现

  • 并查集的初始状态设置:在这里插入图片描述
  • 简单的代码实现:
#include <iostream>
#include <vector>
#include <string>//采用适配器模式实现并查
class UnionFindSet
{
public://构造函数参数为并查集中的元素个数,并查集的初始状态为size颗树构成的森林(size个连通分量)UnionFindSet(size_t size):_SetMap(size,-1){}//给定一个并查集元素找到其所在的(连通分量)多叉树的根结点size_t FindRoot(int Node) const throw(std :: string){//越界检查if (Node < 0 || Node >= _SetMap.size())throw "Label out of range";	while (_SetMap[Node] >= 0){Node = _SetMap[Node];}return static_cast<size_t>(Node);}//给定两个并查集元素,将它们所在的(连通分量)多叉树进行合并运算void Union(int Node1, int Node2)  throw(std::string){//越界检查if (Node1 < 0 || Node1 > _SetMap.size()|| Node2 < 0 || Node2 > _SetMap.size())throw "Label out of range";//先找到两个元素所在的(连通分量)多叉树的根size_t root1 = FindRoot(Node1);size_t root2 = FindRoot(Node2);//进行多叉树合并操作if (root1 != root2){_SetMap[root1] += _SetMap[root2];_SetMap[root2] = static_cast<int>(root1);}}//计算并查集中多叉树的颗数(连通分量的个数)size_t SetCount() const noexcept{//并查集中多叉树的颗数就是vector中负数元素的个数size_t count = 0;for (auto e : _SetMap){if (e < 0)++count;}return count;}
private:std::vector<int> _SetMap;
};
  • 并查集是一种经常用于划分等价类的数据结构.以树形逻辑结构为基础,以一颗多叉树(一个连通分量)表示一个等价类,多个互相不连通的多叉树(连通分量)构成的森林用于表示多个等价类构成的集合,使用并查集可以很好地解决等价类的划分和计数问题(即图的连通分量的求解问题)

三.并查集的基本应用

LeetCoed : LCR 116. 省份数量

  • 这个问题就是一个等价类集合构建和计数问题,可以使用并查集解决.(题目中的相连关系就是一种相对于相同省份性质的等价关系)
  • 问题的本质可以抽象为:以城市为元素依据相连关系形成的图结构的最小生成树的个数(即连通分量的个数),可以采用dfsbfs遍历算法,此处提供使用并查集的一种写法.
  • 借助vectorlambda表达式建立简单的并查集最后返回并查集中多叉树的个数:
class Solution 
{
public:int findCircleNum(vector<vector<int>>& isConnected) {//创建简易的并查集vector<int> UnionSet(isConnected.size(),-1);//定义Find函数,根据结点找到多叉树的根auto Find = [&UnionSet](int Node){while(UnionSet[Node] >=0){Node = UnionSet[Node];}return Node;};for(int i = 0; i < isConnected.size(); ++i){for(int j = i+1; j < isConnected.size(); ++j){if(isConnected[i][j] == 1){//多叉树合并int root1 = Find(i);int root2 = Find(j);if(root1 != root2){UnionSet[root1] += UnionSet[root2];//这句代码用于修改结点计数,此题中可以不加UnionSet[root2] = root1;}}}}int count = 0;//统计并查集中多叉树的个数for(auto e : UnionSet){if(e < 0 ) ++count;}return count;}
};

LeetCode:990. 等式方程的可满足性

  • 这同样是一个等价类划分的问题:将0~25的各个编号与a~z二十六个字母建立映射关系,根据字母间相等关系构建并查集:
class Solution 
{
public:bool equationsPossible(vector<string>& equations) {vector<int> UionSet(26,-1);auto FindRoot = [&UionSet](int Node){while(UionSet[Node] >= 0){Node = UionSet[Node];}return Node;};//先遍历等式方程中的字母,在并查集中将它们归类到各个多叉树中(构建相等关系等价类集合)for(auto str : equations){//遇到等式,等式两边字母应该属于并查集中同一颗多叉树if(str[1] == '='){int root1 = FindRoot(str[0]-'a');int root2 = FindRoot(str[3]-'a');if(root1 != root2){UionSet[root1] += UionSet[root2];UionSet[root2] = root1;}}}//再处理不等式方程,检验相容性for(auto str : equations){//遇到不等式,不等式两边字母不能属于并查集中同一颗多叉树if(str[1] == '!'){int root1 = FindRoot(str[0]-'a');int root2 = FindRoot(str[3]-'a');if(root1 == root2){return false;}}}return true;}
};

在这里插入图片描述

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/101289.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【Redis】——Redis基础的数据结构以及应用场景

什么是redis数据库 Redis 是一种基于内存的数据库&#xff0c;对数据的读写操作都是在内存中完成&#xff0c;因此读写速度非常快&#xff0c;常用于缓存&#xff0c;消息队列、分布式锁等场景。&#xff0c;Redis 还支持 事务 、持久化、Lua 脚本、多种集群方案&#xff08;主…

Centos7卸载|安装JDK1.8|Xshell7批量控制多个终端

一: 使用yum安装的好处是较为方便|环境变量自动配置完成。 1.1: 执行下面的命令,检查是否已安装了jdk # 查看当前是否安装了JDK&#xff0c; [rootwww ~]# rpm -qa |grep java [rootwww ~]# rpm -qa |grep jdk [rootwww ~]# rpm -qa |grep gcj [rootwww ~]# rpm -qa | grep -…

数据结构——二叉搜索树(附带C++实现版本)

文章目录 二叉搜索树概念 二叉树的实际应用二叉树模拟实现存储结构二叉搜索树构成二叉搜索树的查找插入操作中序遍历二叉树的删除循环(利用左子树最右节点&#xff09;递归(利用右子树根节点) 二叉树拷贝二叉树资源的销毁 二叉树实现完整代码总结 二叉搜索树 概念 二叉搜索树…

PHPStudy 安装tp8 php8.2.9

一、PhpStudy升级PHP版本&#xff0c;安装PHP8.2操作步骤 1.1、官网下载最新的php版本 打开Windows版的官网下载&#xff0c;地址&#xff1a;https://windows.php.net/download/ 页面上有不同的PHP版本&#xff0c;这里我们下载的是64位nts版的PHP8.2.9。 1.2、解压下载的文…

2023.8 - java - 泛型

泛型问题的引出&#xff1a; jdk 1.5 引出泛型 // package 泛型; public class index {public static void main (String[] args){test t new test();t.setContent("aaa");int a (int) t.getContent();System.out.println(a);} }class test{Object content;publi…

国内常见的几款可视化Web组态软件

组态软件是一种用于控制和监控各种设备的软件&#xff0c;也是指在自动控制系统监控层一级的软件平台和开发环境。这类软件实际上也是一种通过灵活的组态方式&#xff0c;为用户提供快速构建工业自动控制系统监控功能的、通用层次的软件工具。通常用于工业控制&#xff0c;自动…

[SWPUCTF 2022 新生赛]ez_ez_php

这段代码是一个简单的PHP文件处理脚本。让我们逐行进行分析&#xff1a; error_reporting(0); - 这行代码设置了错误报告的级别为0&#xff0c;意味着不显示任何错误。 if (isset($_GET[file])) { - 这行代码检查是否存在一个名为"file"的GET参数。 if ( substr($_…

无涯教程-Perl - wantarray函数

描述 如果当前正在执行的函数的context正在寻找列表值,则此函数返回true。在标量context中返回false。 语法 以下是此函数的简单语法- wantarray返回值 如果没有context,则此函数返回undef&#xff1b;如果lvalue需要标量,则该函数返回0。 例 以下是显示其基本用法的示例…

记录Taro巨坑,找不到sass类型定义文件

问题 taronutuisassts项目里tsconfig.json一直报红报错。 找不到“sass”的类型定义文件。 程序包含该文件是因为: 隐式类型库 “sass” 的入口点 其实正常人想的肯定是装上 types/sass试试。开始我试过了&#xff0c;没用。删了依赖重装也没用。后面在issue中找到答案了 解决…

Mybatis的SqlSource SqlNode BoundSql

学习链接 MyBatis SqlSource解析 【Mybatis】Mybatis源码之SqlSource#getBoundSql获取预编译SQL Mybatis中SqlSource解析流程详解 Mybatis TypeHandler解析 图解 Mybatis的SqlSource&SqlNode - processon DynamicSqlSource public class DynamicSqlSource implement…

05-微信小程序常用组件-表单组件

05-微信小程序常用组件-表单组件 文章目录 表单组件button 按钮案例代码 form 表单案例代码 image 图片支持长按识别的码案例代码 微信小程序包含了六大组件&#xff1a; 视图容器、 基础内容、 导航、 表单、 互动和 导航。这些组件可以通过WXML和WXSS进行布局和样式设…

800V高压电驱动系统架构分析

需要电驱竞品样件请联&#xff1a;shbinzer &#xff08;拆车邦&#xff09; 过去一年是新能源汽车市场爆发的一年&#xff0c;据中汽协数据&#xff0c;2021年新能源汽车销售352万辆&#xff0c;同比大幅增长157.5%。新能源汽车技术发展迅速&#xff0c;畅销车辆在动力性能…

【Python原创设计】基于Python Flask的全国气象数据采集及可视化系统-附下载方式以及项目参考论文,原创项目其他均为抄袭

基于Python Flask的全国气象数据采集及可视化系统 一、项目简介二、项目技术三、项目功能四、运行截图五、分类说明六、实现代码七、数据库结构八、源码下载 一、项目简介 本项目是一个基于Web技术的实时气象数据可视化系统。通过爬取中国天气网的各个城市气象数据&#xff0c…

Nginx高可用集群

目录 一.简介二.案例1.实现思路2.配置文件修改3.实现效果故障转移机制 一.简介 以提高应用系统的可靠性&#xff0c;尽可能地减少中断时间为目标&#xff0c;确保服务的连续性&#xff0c;达到高可用的容错效果。例如“故障切换”、“双机热备”、“多机热备”等都属于高可用集…

ceph集群的扩容缩容

文章目录 集群扩容添加osd使用ceph-deploy工具手动添加 添加节点新节点前期准备新节点安装ceph&#xff0c;出现版本冲突 ceph-deploy增加节点 集群缩容删除osd删除节点 添加monitor节点删除monitor节点使用ceph-deploy卸载集群 实验所用虚拟机均为Centos 7.6系统&#xff0c;8…

windows系统丢失mfc120u.dll的解决方法

1.mfc120u.dll是什么 mfc120u.dll是Windows操作系统中的一个动态链接库&#xff08;Dynamic Link Library&#xff0c;简称DLL&#xff09;文件。它包含了一些用于运行C程序的函数和其他资源。这个特定的DLL文件是Microsoft Foundation Classes&#xff08;MFC&#xff09;库的…

【数据结构OJ题】相交链表

原题链接&#xff1a;https://leetcode.cn/problems/intersection-of-two-linked-lists/description/ 目录 1. 题目描述 2. 思路分析 3. 代码实现 1. 题目描述 2. 思路分析 看到这道题&#xff0c;很容易想到的方法就是暴力求解&#xff0c;就是将一个链表的每个结点的地址…

曲线救国 | 双非渣硕的秋招路

作者 | 带带大兄弟 面试锦囊之面经分享系列&#xff0c;持续更新中 欢迎后台回复"面试"加入讨论组交流噢 一篇旧文&#xff0c;可以参考~ 写在前面 双非渣硕&#xff0c;0实习&#xff0c;3篇水文&#xff0c;三个给老板当打工仔的nlp横向项目&#xff0c;八月份开…

文本三剑客之sed编辑器

sed 一、sed简介1.1 什么是sed&#xff1f;1.2 sed原理1.3 sed核心功能 二、sed命令格式详解2.1 命令格式2.2 常用选项2.3 sed脚本语法2.3.1 基本语法结构2.3.2 地址部分-----指定匹配范围2.3.3 命令部分-----要执行的命令 三、sed查找替换3.1 基本语法3.2 分组后向引用3.3 变量…

【面试八股文】每日一题:谈谈你对线程的理解

每日一题-Java核心-谈谈你对线程的理解【面试八股文】 Java线程是Java程序中的执行单元。一个Java程序可以同时运行多个线程&#xff0c;每个线程可以独立执行不同的任务。线程的执行是并发的&#xff0c;即多个线程可以同时执行。 1. 线程的特点 Java中的线程有如下的特点 轻…