当前位置: 首页 > 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.实验拓扑 搭建 …...

C++_核心编程_多态案例二-制作饮品

#include <iostream> #include <string> using namespace std;/*制作饮品的大致流程为&#xff1a;煮水 - 冲泡 - 倒入杯中 - 加入辅料 利用多态技术实现本案例&#xff0c;提供抽象制作饮品基类&#xff0c;提供子类制作咖啡和茶叶*//*基类*/ class AbstractDr…...

3403. 从盒子中找出字典序最大的字符串 I

3403. 从盒子中找出字典序最大的字符串 I 题目链接&#xff1a;3403. 从盒子中找出字典序最大的字符串 I 代码如下&#xff1a; class Solution { public:string answerString(string word, int numFriends) {if (numFriends 1) {return word;}string res;for (int i 0;i &…...

C++八股 —— 单例模式

文章目录 1. 基本概念2. 设计要点3. 实现方式4. 详解懒汉模式 1. 基本概念 线程安全&#xff08;Thread Safety&#xff09; 线程安全是指在多线程环境下&#xff0c;某个函数、类或代码片段能够被多个线程同时调用时&#xff0c;仍能保证数据的一致性和逻辑的正确性&#xf…...

稳定币的深度剖析与展望

一、引言 在当今数字化浪潮席卷全球的时代&#xff0c;加密货币作为一种新兴的金融现象&#xff0c;正以前所未有的速度改变着我们对传统货币和金融体系的认知。然而&#xff0c;加密货币市场的高度波动性却成为了其广泛应用和普及的一大障碍。在这样的背景下&#xff0c;稳定…...

基于SpringBoot在线拍卖系统的设计和实现

摘 要 随着社会的发展&#xff0c;社会的各行各业都在利用信息化时代的优势。计算机的优势和普及使得各种信息系统的开发成为必需。 在线拍卖系统&#xff0c;主要的模块包括管理员&#xff1b;首页、个人中心、用户管理、商品类型管理、拍卖商品管理、历史竞拍管理、竞拍订单…...

Ubuntu系统多网卡多相机IP设置方法

目录 1、硬件情况 2、如何设置网卡和相机IP 2.1 万兆网卡连接交换机&#xff0c;交换机再连相机 2.1.1 网卡设置 2.1.2 相机设置 2.3 万兆网卡直连相机 1、硬件情况 2个网卡n个相机 电脑系统信息&#xff0c;系统版本&#xff1a;Ubuntu22.04.5 LTS&#xff1b;内核版本…...

从零开始了解数据采集(二十八)——制造业数字孪生

近年来&#xff0c;我国的工业领域正经历一场前所未有的数字化变革&#xff0c;从“双碳目标”到工业互联网平台的推广&#xff0c;国家政策和市场需求共同推动了制造业的升级。在这场变革中&#xff0c;数字孪生技术成为备受关注的关键工具&#xff0c;它不仅让企业“看见”设…...

Mysql故障排插与环境优化

前置知识点 最上层是一些客户端和连接服务&#xff0c;包含本 sock 通信和大多数jiyukehuduan/服务端工具实现的TCP/IP通信。主要完成一些简介处理、授权认证、及相关的安全方案等。在该层上引入了线程池的概念&#xff0c;为通过安全认证接入的客户端提供线程。同样在该层上可…...

Easy Excel

Easy Excel 一、依赖引入二、基本使用1. 定义实体类&#xff08;导入/导出共用&#xff09;2. 写 Excel3. 读 Excel 三、常用注解说明&#xff08;完整列表&#xff09;四、进阶&#xff1a;自定义转换器&#xff08;Converter&#xff09; 其它自定义转换器没生效 Easy Excel在…...

STM32 低功耗设计全攻略:PWR 模块原理 + 睡眠 / 停止 / 待机模式实战(串口 + 红外 + RTC 应用全解析)

文章目录 PWRPWR&#xff08;电源控制模块&#xff09;核心功能 电源框图上电复位和掉电复位可编程电压监测器低功耗模式模式选择睡眠模式停止模式待机模式 修改主频一、准备工作二、修改主频的核心步骤&#xff1a;宏定义配置三、程序流程&#xff1a;时钟配置函数解析四、注意…...