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(并查集理论基础、寻找存在的路径)
并查集理论基础 基础内容 并查集常用来解决连通性问题,主要有两个功能: 将两个元素添加到一个集合中判断两个元素在不在同一个集合 将三个元素A,B,C (分别是数字)放在同一个集合,其实就是将…...
鸿蒙next选择 Flutter 开发跨平台应用的原因
在移动操作系统的竞争中,鸿蒙(HarmonyOS)自从发布以来便吸引了广泛的关注。作为华为主导的操作系统,鸿蒙的设计初衷是打破平台壁垒,实现设备间的无缝连接与应用共享。然而,要实现这一目标,仅仅依…...
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这个网页中有搜索关键词 对指定网址进行监控,这里可以对ip进行扫描&…...
FTP、ISCSI、CHRONY、DNS、NFS、DOCKER、MARIADB、NGINX、PHP、CA各服务开启方法
2.1 FTP 服务 (vsftpd) 安装 vsftpd: sudo yum install vsftpd -y 启动并设置开机自启: sudo systemctl start vsftpdsudo systemctl enable vsftpd 配置文件位于 /etc/vsftpd/vsftpd.conf,可根据需要修改配置。 2.2 SCSI 服务 SCSI 配…...
抢先体验AI领域的新宠儿:Llama3.1,部署实战探索!
本文简介 就在今天,Meta 发布了 Llama 3.1,这次带来的中杯、大杯和超大杯3个版本。 从纸面数据来看,Llama 3.1 超大杯已经能跟 GPT-4 Omni、Claude 3.5 Sonnet 分庭抗礼了。 而中杯和大杯更是将同量级的对手摁在地上摩擦。 要知道ÿ…...
HarmonyOS基础:鸿蒙系统组件导航Navigation
大家好!我是黑臂麒麟(起名原因:一个出生全右臂自带纹身的高质量程序员😏),也是一位6(约2个半坤年)的前端; 学习如像练武功一样,理论和实践要相结合࿰…...
【K8S问题系列】Kubernetes 中 Pod 无法通过 Service 名称访问服务的 DNS 解析失败【已解决】
在 Kubernetes 中,Service 提供了一种稳定的方式,通过名称访问一组 Pod。当其他 Pod 无法通过 Service 名称访问服务,并且出现 DNS 解析失败时,通常会导致应用无法正常工作。本文将详细分析此问题的常见原因及其解决方案。 一、问…...
【下载工具】Internet Download Manager下载器介绍
Internet Download Manager(简称IDM)作为一款功能强大的下载管理软件,以其高效、稳定的特点受到了广大用户的青睐。本文将为您详细介绍IDM的功能特性以及具体的使用方法。 功能特性 加速下载:IDM通过多线程下载技术,…...
如何打开/关闭 GitLab 的版本检查功能?
本文分享如何打开/关闭 GitLab 的版本检查功能。 极狐GitLab 是 GitLab 的中国发行版【https://dl.gitlab.cn/ncecn6kb】,中文版本对中国用户更友好,文章以私有化部署的极狐GitLab 实例来演示版本检查功能的开启和关闭。强烈不建议关闭该功能࿰…...
java-web-day13-事务管理+spring aop
事务管理: 事务回滚 默认情况下,只有出现runtimeException(运行时异常)才回滚, 而如果出现其他异常,例如受检异常, 就不会回滚事务, 不过可以加上rollbackfor属性用于控制出现何种异常类型, 回滚事务 事务传播: 当一个事务方法被另一个事务方法调用时, 这个事务方法应该如何进行…...
MySQL详细安装教程
一、从MySQL官网安装 可以翻译成中文看起来就舒服多了 下载并打开安装包,能看到版本是8.0.36,双击运行或者右键选择打开,打开后是一个安装向导,这个安装向导会先帮我们安装一个 mysql-installer 的程序,再通过该程序安…...
文件系统和日志管理
一、文件系统 1.概述 文件系统:文件系统提供了一个接口,用户用来访问硬件设备(硬盘)。硬件设备上对文件的管理。文件存储在硬盘上,硬盘最小的存储单位是512字节(扇区)。文件在硬盘上的最小存储…...
【LeetCode】【算法】208. 实现 Trie (前缀树)
LeetCode 208. 实现 Trie (前缀树) 题目描述 Trie(发音类似 “try”)或者说 前缀树 是一种树形数据结构,用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景,例如自动补全和拼写检查。 请你实现 Trie 类&…...
libaom 源码分析:帧间运动矢量预测
AV1 帧间运动矢量预测原理 运动矢量可以被相邻块预测,这些相邻块可以是空域相邻块,或位于参考帧中的时域相邻块;通过检查所有这些块,将确定一组运动矢量预测器,并用于编码运动矢量信息。空域运动矢量预测 两组空域相邻块可以被利用寻找空域 MV 预测器,第一组包括当前块的…...
Android TextView自动换行文本显示不全解决
某些情况下,TextView自动换行后,会出现每行结尾处显示不全的问题, 如图: 常见解决方案: 设置TextView的“ellipsize”属性为“end” 实测无效!将TextView外部的Layout改为RelativeLayout 实测无效&…...
【LeetCode】【算法】394. 字符串解码
LeetCode 394. 字符串解码 题目描述 给定一个经过编码的字符串,返回它解码后的字符串。 编码规则为: k[encoded_string],表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。 你可以认为输入字符串总是有效的;输入字…...
最新整理:Selenium自动化测试面试题
1.selenium中如何判断元素是否存在? find_elements查找到的元素个数为0,find_element报错意味着元素不存在 2.如何判断元素是否出现? 判断元素是否出现,存在两种情况,一种是该元素压根就没有,自然不会出现;另外一种是有这样的…...
外包干了2年,快要废了。。。
先说一下自己的情况,普通本科,在外包干了2年多的功能测试,这几年因为大环境不好,我整个人心惊胆战的,怕自己卷铺盖走人了,我感觉自己不能够在这样蹉跎下去了,长时间呆在一个舒适的环境真的会让一…...
乐尚代驾十订单支付seata、rabbitmq异步消息、redisson延迟队列
账单信息 司机结束代驾之后,生成账单(包含账单信息和分账信息)司机发送账单给乘客乘客获取账单之后,进行支付 获取账单信息 order_bill表记录的账单信息,我们直接获取即可 Operation(summary "根据订单id获取…...
HCIP--3实验- 链路聚合,VLAN间通讯,Super VLAN,MSTP,VRRPip配置,静态路由,环回,缺省,空接口,NAT
学习目标: 链路聚合VLAN间通讯Super VLANMSTPVRRPip配置,静态路由,环回,缺省,空接口NAT 学习内容: 实验拓扑实验需求实验需求分析实验配置内容 (每一个设备的每一步操作)实验结果验证 1.实验拓扑 搭建 …...
lite-avatar形象库入门:如何查找、预览并下载心仪的数字人形象
lite-avatar形象库入门:如何查找、预览并下载心仪的数字人形象 1. 数字人形象库简介 在数字人项目开发中,一个合适的虚拟形象往往能让用户体验大幅提升。lite-avatar形象库正是为解决这一需求而生的专业资源库。 这个基于HumanAIGC-Engineering/LiteA…...
注意力机制融合新范式:从GCNet与DANet看全局建模的演进与实战
1. 视觉注意力机制的进化之路 记得我第一次接触视觉注意力机制是在2016年,那时ResNet刚掀起深度学习的新浪潮。当时最让我困惑的是:为什么神经网络需要"注意力"?后来在ImageNet数据集上做实验时才明白,传统CNN就像近视眼…...
AI虚拟员工平台完整搭建教程:从源码获取到正式上线,全流程记录
温馨提示:文末有资源获取方式最近AI赛道又火了一个新方向,很多人都在讨论,但真正能用起来的没几个。技术门槛摆在那,普通用户想上手确实不容易。今天这篇教程,我把从源码部署到正式上线的完整过程整理出来,…...
Windows 11终极清理优化指南:用Win11Debloat快速提升系统性能
Windows 11终极清理优化指南:用Win11Debloat快速提升系统性能 【免费下载链接】Win11Debloat 一个简单的PowerShell脚本,用于从Windows中移除预装的无用软件,禁用遥测,从Windows搜索中移除Bing,以及执行各种其他更改以…...
如何用League-Toolkit提升你的英雄联盟游戏体验
如何用League-Toolkit提升你的英雄联盟游戏体验 【免费下载链接】League-Toolkit 兴趣使然的、简单易用的英雄联盟工具集。支持战绩查询、自动秒选等功能。基于 LCU API。 项目地址: https://gitcode.com/gh_mirrors/le/League-Toolkit 你是否曾经在英雄联盟游戏中感到效…...
OpenClaw+ollama-QwQ-32B实战:自动化处理100份简历筛选
OpenClawollama-QwQ-32B实战:自动化处理100份简历筛选 1. 为什么选择自动化简历筛选 去年团队扩张时,我作为技术负责人参与了简历初筛工作。面对雪片般飞来的PDF简历,连续三天熬夜到凌晨两点手动整理关键信息后,我意识到必须寻找…...
so-vits-svc声压级标准化终极指南:如何避免AI语音转换中的音频质量损伤
so-vits-svc声压级标准化终极指南:如何避免AI语音转换中的音频质量损伤 【免费下载链接】so-vits-svc SoftVC VITS Singing Voice Conversion 项目地址: https://gitcode.com/gh_mirrors/so/so-vits-svc so-vits-svc作为当前最先进的AI歌声转换框架ÿ…...
Nemo文件管理器终极指南:Cinnamon桌面环境下的高效文件管理神器
Nemo文件管理器终极指南:Cinnamon桌面环境下的高效文件管理神器 【免费下载链接】nemo File browser for Cinnamon 项目地址: https://gitcode.com/gh_mirrors/ne/nemo Nemo是Cinnamon桌面环境的官方文件管理器,作为一个免费开源的软件项目&#…...
环境感知驱动的EFI构建:让OpenCore配置效率提升300%
环境感知驱动的EFI构建:让OpenCore配置效率提升300% 【免费下载链接】OpCore-Simplify A tool designed to simplify the creation of OpenCore EFI 项目地址: https://gitcode.com/GitHub_Trending/op/OpCore-Simplify OpenCore配置(OpenCore是一…...
课堂教学质量综合评分系统
目录 一、项目环境与目录结构 1. 环境要求 2. 推荐目录结构 二、核心类设计:ClassroomScorer 三、关键代码深度解析 1. 基础路径配置 2. 初始化方法:极致灵活的配置 3. 上下文管理器:统一封装 CSV 读取 4. 数据加载:4 类 …...
