当前位置: 首页 > news >正文

day53 图论章节刷题Part05(并查集理论基础、寻找存在的路径)

并查集理论基础

基础内容

并查集常用来解决连通性问题,主要有两个功能:

  • 将两个元素添加到一个集合中
  • 判断两个元素在不在同一个集合

将三个元素A,B,C (分别是数字)放在同一个集合,其实就是将三个元素连通在一起,只需要用一个一维数组来表示,即:father[A] = B,father[B] = C (有向连通图)。对ABC进行寻根,如果都是C,说明在同一个集合里。 此时需要初始化father[C] = C

路径压缩

由于搜索过程像是一个多叉树中从叶子到根节点的过程,如果多叉树高度很深的话,每次find函数寻找根的过程就要递归很多次。所以将除了根节点其他所有节点都挂载根节点下,在寻根的时候就很快。

路径压缩的核心思想是在查找某个节点的根节点时,将沿途的所有节点直接连接到根节点。

并查集模版C++

int n = 1005; // n根据题目中节点数量而定,一般比节点数量大一点就好
vector<int> father = vector<int> (n, 0); // C++里的一种数组结构// 并查集初始化
void init() {for (int i = 0; i < n; ++i) {father[i] = i;}
}
// 并查集里寻根的过程
int find(int u) {return u == father[u] ? u : father[u] = find(father[u]); // 路径压缩
}// 判断 u 和 v是否找到同一个根
bool isSame(int u, int v) {u = find(u);v = find(v);return u == v;
}// 将v->u 这条边加入并查集
void join(int u, int v) {u = find(u); // 寻找u的根v = find(v); // 寻找v的根if (u == v) return ; // 如果发现根相同,则说明在一个集合,不用两个节点相连直接返回father[v] = u;
}

并查集主要有三个功能:

  • 寻找根节点,函数:find(int u),也就是判断这个节点的祖先节点是哪个
  • 将两个节点接入到同一个集合,函数:join(int u, int v),将两个节点连在同一个根节点上
  • 判断两个节点是否在同一个集合,函数:isSame(int u, int v),就是判断两个节点是不是同一个根节点

寻找存在的路径

对模版的直接应用,学习一下如何使用Java表示模版

import java.util.*;
public class Main{public static void main (String[] args) {Scanner scan=new Scanner(System.in);int n=scan.nextInt();int m=scan.nextInt();DisJoint disJoint=new DisJoint(n+1);for(int i=0;i<m;i++){disJoint.join(scan.nextInt(),scan.nextInt());}if(disJoint.isSame(scan.nextInt(),scan.nextInt())) System.out.println("1");else System.out.println("0");}
}class DisJoint{private int[] father;public DisJoint(int N){father=new int[N];for(int i=0;i<N;i++){father[i]=i;}}public int find(int n){return n==father[n]?n:(father[n]=find(father[n]));}public void join(int u,int v){u=find(u);v=find(v);if(u==v) return;father[v]=u;}public boolean isSame(int u,int v){u=find(u);v=find(v);return u==v;}
}

相关文章:

day53 图论章节刷题Part05(并查集理论基础、寻找存在的路径)

并查集理论基础 基础内容 并查集常用来解决连通性问题&#xff0c;主要有两个功能&#xff1a; 将两个元素添加到一个集合中判断两个元素在不在同一个集合 将三个元素A&#xff0c;B&#xff0c;C &#xff08;分别是数字&#xff09;放在同一个集合&#xff0c;其实就是将…...

鸿蒙next选择 Flutter 开发跨平台应用的原因

在移动操作系统的竞争中&#xff0c;鸿蒙&#xff08;HarmonyOS&#xff09;自从发布以来便吸引了广泛的关注。作为华为主导的操作系统&#xff0c;鸿蒙的设计初衷是打破平台壁垒&#xff0c;实现设备间的无缝连接与应用共享。然而&#xff0c;要实现这一目标&#xff0c;仅仅依…...

shodan6-7---清风

shodan6-7 1.shodan网页版 以cve-2019-0708漏洞指纹特征为例 "\x03\x00\x00\x0b\x06\xd0\x00\x00\x124\x00"在这里插入图片描述 搜索命令参考 https://www.shodan.io/search/filters这个网页中有搜索关键词 对指定网址进行监控&#xff0c;这里可以对ip进行扫描&…...

FTP、ISCSI、CHRONY、DNS、NFS、DOCKER、MARIADB、NGINX、PHP、CA各服务开启方法

2.1 FTP 服务 (vsftpd) 安装 vsftpd&#xff1a; sudo yum install vsftpd -y 启动并设置开机自启&#xff1a; sudo systemctl start vsftpdsudo systemctl enable vsftpd 配置文件位于 /etc/vsftpd/vsftpd.conf&#xff0c;可根据需要修改配置。 2.2 SCSI 服务 SCSI 配…...

抢先体验AI领域的新宠儿:Llama3.1,部署实战探索!

本文简介 就在今天&#xff0c;Meta 发布了 Llama 3.1&#xff0c;这次带来的中杯、大杯和超大杯3个版本。 从纸面数据来看&#xff0c;Llama 3.1 超大杯已经能跟 GPT-4 Omni、Claude 3.5 Sonnet 分庭抗礼了。 而中杯和大杯更是将同量级的对手摁在地上摩擦。 要知道&#xff…...

HarmonyOS基础:鸿蒙系统组件导航Navigation

大家好&#xff01;我是黑臂麒麟&#xff08;起名原因&#xff1a;一个出生全右臂自带纹身的高质量程序员&#x1f60f;&#xff09;&#xff0c;也是一位6&#xff08;约2个半坤年&#xff09;的前端&#xff1b; 学习如像练武功一样&#xff0c;理论和实践要相结合&#xff0…...

【K8S问题系列】Kubernetes 中 Pod 无法通过 Service 名称访问服务的 DNS 解析失败【已解决】

在 Kubernetes 中&#xff0c;Service 提供了一种稳定的方式&#xff0c;通过名称访问一组 Pod。当其他 Pod 无法通过 Service 名称访问服务&#xff0c;并且出现 DNS 解析失败时&#xff0c;通常会导致应用无法正常工作。本文将详细分析此问题的常见原因及其解决方案。 一、问…...

【下载工具】Internet Download Manager下载器介绍

Internet Download Manager&#xff08;简称IDM&#xff09;作为一款功能强大的下载管理软件&#xff0c;以其高效、稳定的特点受到了广大用户的青睐。本文将为您详细介绍IDM的功能特性以及具体的使用方法。 功能特性 加速下载&#xff1a;IDM通过多线程下载技术&#xff0c;…...

如何打开/关闭 GitLab 的版本检查功能?

本文分享如何打开/关闭 GitLab 的版本检查功能。 极狐GitLab 是 GitLab 的中国发行版【https://dl.gitlab.cn/ncecn6kb】&#xff0c;中文版本对中国用户更友好&#xff0c;文章以私有化部署的极狐GitLab 实例来演示版本检查功能的开启和关闭。强烈不建议关闭该功能&#xff0…...

java-web-day13-事务管理+spring aop

事务管理: 事务回滚 默认情况下,只有出现runtimeException(运行时异常)才回滚, 而如果出现其他异常,例如受检异常, 就不会回滚事务, 不过可以加上rollbackfor属性用于控制出现何种异常类型, 回滚事务 事务传播: 当一个事务方法被另一个事务方法调用时, 这个事务方法应该如何进行…...

MySQL详细安装教程

一、从MySQL官网安装 可以翻译成中文看起来就舒服多了 下载并打开安装包&#xff0c;能看到版本是8.0.36&#xff0c;双击运行或者右键选择打开&#xff0c;打开后是一个安装向导&#xff0c;这个安装向导会先帮我们安装一个 mysql-installer 的程序&#xff0c;再通过该程序安…...

文件系统和日志管理

一、文件系统 1.概述 文件系统&#xff1a;文件系统提供了一个接口&#xff0c;用户用来访问硬件设备&#xff08;硬盘&#xff09;。硬件设备上对文件的管理。文件存储在硬盘上&#xff0c;硬盘最小的存储单位是512字节&#xff08;扇区&#xff09;。文件在硬盘上的最小存储…...

【LeetCode】【算法】208. 实现 Trie (前缀树)

LeetCode 208. 实现 Trie (前缀树) 题目描述 Trie&#xff08;发音类似 “try”&#xff09;或者说 前缀树 是一种树形数据结构&#xff0c;用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景&#xff0c;例如自动补全和拼写检查。 请你实现 Trie 类&…...

libaom 源码分析:帧间运动矢量预测

AV1 帧间运动矢量预测原理 运动矢量可以被相邻块预测,这些相邻块可以是空域相邻块,或位于参考帧中的时域相邻块;通过检查所有这些块,将确定一组运动矢量预测器,并用于编码运动矢量信息。空域运动矢量预测 两组空域相邻块可以被利用寻找空域 MV 预测器,第一组包括当前块的…...

Android TextView自动换行文本显示不全解决

某些情况下&#xff0c;TextView自动换行后&#xff0c;会出现每行结尾处显示不全的问题&#xff0c; 如图&#xff1a; 常见解决方案&#xff1a; 设置TextView的“ellipsize”属性为“end” 实测无效&#xff01;将TextView外部的Layout改为RelativeLayout 实测无效&…...

【LeetCode】【算法】394. 字符串解码

LeetCode 394. 字符串解码 题目描述 给定一个经过编码的字符串&#xff0c;返回它解码后的字符串。 编码规则为: k[encoded_string]&#xff0c;表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。 你可以认为输入字符串总是有效的&#xff1b;输入字…...

最新整理:Selenium自动化测试面试题

1.selenium中如何判断元素是否存在? find_elements查找到的元素个数为0&#xff0c;find_element报错意味着元素不存在 2.如何判断元素是否出现? 判断元素是否出现&#xff0c;存在两种情况&#xff0c;一种是该元素压根就没有&#xff0c;自然不会出现;另外一种是有这样的…...

外包干了2年,快要废了。。。

先说一下自己的情况&#xff0c;普通本科&#xff0c;在外包干了2年多的功能测试&#xff0c;这几年因为大环境不好&#xff0c;我整个人心惊胆战的&#xff0c;怕自己卷铺盖走人了&#xff0c;我感觉自己不能够在这样蹉跎下去了&#xff0c;长时间呆在一个舒适的环境真的会让一…...

乐尚代驾十订单支付seata、rabbitmq异步消息、redisson延迟队列

账单信息 司机结束代驾之后&#xff0c;生成账单&#xff08;包含账单信息和分账信息&#xff09;司机发送账单给乘客乘客获取账单之后&#xff0c;进行支付 获取账单信息 order_bill表记录的账单信息&#xff0c;我们直接获取即可 Operation(summary "根据订单id获取…...

HCIP--3实验- 链路聚合,VLAN间通讯,Super VLAN,MSTP,VRRPip配置,静态路由,环回,缺省,空接口,NAT

学习目标&#xff1a; 链路聚合VLAN间通讯Super VLANMSTPVRRPip配置,静态路由,环回&#xff0c;缺省&#xff0c;空接口NAT 学习内容&#xff1a; 实验拓扑实验需求实验需求分析实验配置内容 &#xff08;每一个设备的每一步操作&#xff09;实验结果验证 1.实验拓扑 搭建 …...

GD32F4开发板GD-LINK驱动安装与Keil配置全攻略(附常见问题解决)

GD32F4开发板GD-LINK驱动安装与Keil配置全攻略&#xff08;附常见问题解决&#xff09; 第一次拿到GD32F4开发板时&#xff0c;很多开发者都会遇到驱动安装失败、Keil识别不到芯片的问题。这些问题看似简单&#xff0c;却可能让新手折腾好几个小时。本文将用最直白的方式&#…...

基于模糊PID的水下航行器运动控制系统研究——Matlab 2016b及以上软件应用、课程报告...

基于模糊PID的水下航行器运动控制系统研究 1.适用软件Matlab 2016b及以上 2.课程报告6500字左右共16页 3.课程报告小报告仿真仿真视频 4.请结合以下图片水下航行器的运动控制一直是海洋工程领域的热门课题。面对复杂多变的洋流扰动和强非线性的水动力特性&#xff0c;传统PID控…...

[深度解析] AXI4-Stream Register Slice:时序优化的“外科手术刀”

1. 为什么需要AXI4-Stream Register Slice&#xff1f; 在FPGA设计中&#xff0c;时序问题就像血管中的血栓&#xff0c;随时可能让整个系统瘫痪。想象你正在设计一个4K视频处理流水线&#xff0c;每个像素都要经过十几级处理模块。当系统时钟频率提升到300MHz以上时&#xff0…...

【SOC】Fastboot /DFU 烧录镜像

uboot下 使用fastboot 进行 UFS/EMMC/nand 设备烧录的大致流程&#xff1a; board 进入 uboot&#xff08;支持 fastboot&#xff09;&#xff1b; 同时host机器安装上 fastboot 客户端 ; 2者&#xff08;board与host&#xff09;之间通过usb线连接,通过fastboot 协议进行交互…...

VuePress/Hexo博客作者必看:VSCode Paste Image插件路径配置避坑指南

VuePress/Hexo博客作者必看&#xff1a;VSCode Paste Image插件路径配置避坑指南 当你沉浸在VSCode中撰写技术博客时&#xff0c;是否遇到过这样的场景&#xff1a;本地预览时图片显示完美&#xff0c;但一旦部署到线上&#xff0c;所有图片都变成了令人沮丧的404错误&#xff…...

别再手动改配置了!用Flutter的--dart-define实现开发/测试/生产环境一键切换

Flutter多环境配置实战&#xff1a;用--dart-define打造全链路自动化工作流 每次切换环境都要手动修改十几个配置项&#xff1f;还在为不同环境的API地址、应用图标和包名管理头疼&#xff1f;是时候告别这种低效的开发方式了。作为一位经历过无数个深夜调试环境的Flutter开发者…...

QwQ-32B在ollama中的推理效果展示:数学定理推导、算法设计全过程

QwQ-32B在ollama中的推理效果展示&#xff1a;数学定理推导、算法设计全过程 1. 模型简介与部署准备 QwQ-32B是Qwen系列中专注于推理能力的语言模型&#xff0c;与传统指令调优模型相比&#xff0c;它在解决复杂问题和推理任务方面表现突出。这款中等规模模型拥有325亿参数&a…...

BepInEx游戏插件加载器完全指南:从入门到精通Unity游戏扩展工具

BepInEx游戏插件加载器完全指南&#xff1a;从入门到精通Unity游戏扩展工具 【免费下载链接】BepInEx Unity / XNA game patcher and plugin framework 项目地址: https://gitcode.com/GitHub_Trending/be/BepInEx 如何用BepInEx解锁游戏自定义功能&#xff1f;解决玩家…...

新手避坑指南:用DJI NAZA-LITE飞控组装F450无人机,从焊接电调到GPS校准的完整流程

新手避坑指南&#xff1a;用DJI NAZA-LITE飞控组装F450无人机&#xff0c;从焊接电调到GPS校准的完整流程 第一次组装无人机就像玩一场高风险的拼图游戏——每个零件的位置、每根接线的顺序都可能影响最终能否安全起飞。作为过来人&#xff0c;我清楚地记得焊接电调时锡珠飞溅的…...

FLUX.1-dev LoRA微调指南:基于像素幻梦输出数据集训练专属风格

FLUX.1-dev LoRA微调指南&#xff1a;基于像素幻梦输出数据集训练专属风格 1. 前言&#xff1a;为什么需要LoRA微调 在像素艺术创作领域&#xff0c;每个艺术家都渴望拥有独特的视觉风格。FLUX.1-dev作为当前最先进的扩散模型&#xff0c;配合像素幻梦(Pixel Dream Workshop)…...