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

React Native 导航系统实战(React Navigation)

导航系统实战&#xff08;React Navigation&#xff09; React Navigation 是 React Native 应用中最常用的导航库之一&#xff0c;它提供了多种导航模式&#xff0c;如堆栈导航&#xff08;Stack Navigator&#xff09;、标签导航&#xff08;Tab Navigator&#xff09;和抽屉…...

mongodb源码分析session执行handleRequest命令find过程

mongo/transport/service_state_machine.cpp已经分析startSession创建ASIOSession过程&#xff0c;并且验证connection是否超过限制ASIOSession和connection是循环接受客户端命令&#xff0c;把数据流转换成Message&#xff0c;状态转变流程是&#xff1a;State::Created 》 St…...

iPhone密码忘记了办?iPhoneUnlocker,iPhone解锁工具Aiseesoft iPhone Unlocker 高级注册版​分享

平时用 iPhone 的时候&#xff0c;难免会碰到解锁的麻烦事。比如密码忘了、人脸识别 / 指纹识别突然不灵&#xff0c;或者买了二手 iPhone 却被原来的 iCloud 账号锁住&#xff0c;这时候就需要靠谱的解锁工具来帮忙了。Aiseesoft iPhone Unlocker 就是专门解决这些问题的软件&…...

【磁盘】每天掌握一个Linux命令 - iostat

目录 【磁盘】每天掌握一个Linux命令 - iostat工具概述安装方式核心功能基础用法进阶操作实战案例面试题场景生产场景 注意事项 【磁盘】每天掌握一个Linux命令 - iostat 工具概述 iostat&#xff08;I/O Statistics&#xff09;是Linux系统下用于监视系统输入输出设备和CPU使…...

【android bluetooth 框架分析 04】【bt-framework 层详解 1】【BluetoothProperties介绍】

1. BluetoothProperties介绍 libsysprop/srcs/android/sysprop/BluetoothProperties.sysprop BluetoothProperties.sysprop 是 Android AOSP 中的一种 系统属性定义文件&#xff08;System Property Definition File&#xff09;&#xff0c;用于声明和管理 Bluetooth 模块相…...

Springcloud:Eureka 高可用集群搭建实战(服务注册与发现的底层原理与避坑指南)

引言&#xff1a;为什么 Eureka 依然是存量系统的核心&#xff1f; 尽管 Nacos 等新注册中心崛起&#xff0c;但金融、电力等保守行业仍有大量系统运行在 Eureka 上。理解其高可用设计与自我保护机制&#xff0c;是保障分布式系统稳定的必修课。本文将手把手带你搭建生产级 Eur…...

【OSG学习笔记】Day 16: 骨骼动画与蒙皮(osgAnimation)

骨骼动画基础 骨骼动画是 3D 计算机图形中常用的技术&#xff0c;它通过以下两个主要组件实现角色动画。 骨骼系统 (Skeleton)&#xff1a;由层级结构的骨头组成&#xff0c;类似于人体骨骼蒙皮 (Mesh Skinning)&#xff1a;将模型网格顶点绑定到骨骼上&#xff0c;使骨骼移动…...

成都鼎讯硬核科技!雷达目标与干扰模拟器,以卓越性能制胜电磁频谱战

在现代战争中&#xff0c;电磁频谱已成为继陆、海、空、天之后的 “第五维战场”&#xff0c;雷达作为电磁频谱领域的关键装备&#xff0c;其干扰与抗干扰能力的较量&#xff0c;直接影响着战争的胜负走向。由成都鼎讯科技匠心打造的雷达目标与干扰模拟器&#xff0c;凭借数字射…...

Java面试专项一-准备篇

一、企业简历筛选规则 一般企业的简历筛选流程&#xff1a;首先由HR先筛选一部分简历后&#xff0c;在将简历给到对应的项目负责人后再进行下一步的操作。 HR如何筛选简历 例如&#xff1a;Boss直聘&#xff08;招聘方平台&#xff09; 直接按照条件进行筛选 例如&#xff1a…...

Map相关知识

数据结构 二叉树 二叉树&#xff0c;顾名思义&#xff0c;每个节点最多有两个“叉”&#xff0c;也就是两个子节点&#xff0c;分别是左子 节点和右子节点。不过&#xff0c;二叉树并不要求每个节点都有两个子节点&#xff0c;有的节点只 有左子节点&#xff0c;有的节点只有…...