算法打卡:第十一章 图论part05

今日收获:并查集理论基础,寻找存在的路径

1. 并查集理论基础(from代码随想录)

(1)应用场景:判断两个元素是否在同一个集合中

(2)原理讲解:通过一个一维数组,根存储的元素是自己,其他节点存储的元素是自己的上一级元素。在查找时,判断两个元素的根是否相同。

(3)路径压缩:让所有的其他节点都直接存储根节点,避免树的高度太深,递归次数太多

(4)主要功能:

  • 寻找任意节点的根节点;
  • 将两个节点加入同一个集合;
  • 判断两个节点是否在同一个集合;

(5)常见误区:在添加节点时,必须先找到两个节点的根,然后将根相连。

2. 寻找存在的路径

题目链接:107. 寻找存在的路径

思路:将节点用并查集的方式存储,判断两节点是否存在路径就是看这两个节点的根节点是否相同

方法:

import java.util.Scanner;public class Main{public static void main(String[] args){Scanner sc=new Scanner(System.in);// 接收数据int N=sc.nextInt();int M=sc.nextInt();int[] tree=new int[N+1];// 初始化,每个节点都是根节点for (int i=1;i<N+1;i++){tree[i]=i;}// 添加节点for (int i=0;i<M;i++){int s=sc.nextInt();int t=sc.nextInt();int sRoot=find(tree,s);int tRoot=find(tree,t);tree[tRoot]=sRoot;}int source=sc.nextInt();int dest=sc.nextInt();int root1=find(tree,source);int root2=find(tree,dest);if (root1==root2){System.out.println(1);}else {System.out.println(0);}  }// 寻找根节点public static int find(int[] tree, int node){if (tree[node]==node){  // 根节点return node;}return tree[node]=find(tree,tree[node]);}
}

3. 并查集Java模板

主要的方法:寻找根节点,加入并查集,判断是否连接

//并查集模板
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 n, int m) {n = find(n);m = find(m);if (n == m) return;father[m] = n;}public boolean isSame(int n, int m){n = find(n);m = find(m);return n == m;}}

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

如若内容造成侵权/违法违规/事实不符,请联系一条长河网进行投诉反馈,一经查实,立即删除!

相关文章

底盘四轮转向运动学解析(含代码)

目录 写在前面的话四轮转向运动学解析四轮转向理论图解robot_control.py 完整代码关键参数完整代码 公式解析&#xff08;根据代码&#xff09;反相--模式1详细图解 正相--模式2轴心--模式3 写在前面的话 网上找了很多资料&#xff0c;对于四轮转向运动学描述的很少&#xff0…

如何快速免费搭建自己的Docker私有镜像源来解决Docker无法拉取镜像的问题(搭建私有镜像源解决群晖Docker获取注册表失败的问题)

文章目录 📖 介绍 📖🏡 演示环境 🏡📒 Docker无法拉取镜像 📒📒 解决方案 📒🔖 方法一:免费快速搭建自己的Docker镜像源🎈 部署🎈 使用🔖 备用方案⚓️ 相关链接 🚓️📖 介绍 📖 在当前的网络环境下,Docker镜像的拉取问题屡见不鲜(各类Nas查询…

意得辑(Editage)润色全网最低折扣

意得辑(Editage)润色全网最低折扣 优惠代码如图 可以点击我想要咨询&#xff5e; 意得辑论文润色服务优惠代码&#xff5c;提高论文投稿成功率的最佳选择 推荐理由&#xff1a; 意得辑是全球领先的学术论文润色服务平台&#xff0c;特别适合非母语作者。凭借其专业的编辑团队…

买软件服务白送软件产品还送同等价值的白酒或其它商品,我这不是亏到姥姥家了吗?

原创 超云艾艾 AI智造AI编程 2024年09月23日 21:15 北京 在“企业数字化转型、建设和升级面临的主要难题和解决之道”文中&#xff0c;我提到过&#xff0c;针对企业做数字化转型和升级可能遇到的人才、资金和技术问题&#xff0c;我们可以基于SCSAI平台提供的十大功能以及多年…

巴黎嫩事件对数据信息安全的影响及必要措施

2024年9月17日&#xff0c;黎巴嫩首都贝鲁特发生了多起小型无线电通信设备爆炸事件&#xff0c;导致伊朗驻黎巴嫩大使受轻伤。这一事件不仅引发了对安全的广泛关注&#xff0c;也对数据信息安全提出了新的挑战。 王工 18913263502 对数据信息安全的影响&#xff1a; 数据泄露风…

颍川陈氏——平民崛起的典范

园子说颍川 广州有一处老建筑“陈家祠”&#xff0c;豪华精美堪比皇宫&#xff0c;誉为“岭南建筑艺术明珠”、“新世纪羊城八景”之一&#xff0c;是全国文保单位&#xff0c;4A 级景区。主体建筑以中轴线三座厅堂为中心&#xff0c;由大小十九座单体建筑组成&#xff0c;占地…

SpringBoot教程(三十) | SpringBoot集成Shiro权限框架

SpringBoot教程&#xff08;三十&#xff09; | SpringBoot集成Shiro权限框架 一、 什么是Shiro二、Shiro 组件核心组件其他组件 三、流程说明shiro的运行流程 四、SpringBoot 集成 Shiro &#xff08;shiro-spring-boot-web-starter方式&#xff09;1. 添加 Shiro 相关 maven2…

基于SpringBoot+Vue+MySQL的电影院购票管理系统

系统展示 用户前台界面 管理员后台界面 系统背景 随着电影产业的蓬勃发展&#xff0c;电影院已成为人们休闲娱乐的重要场所。然而&#xff0c;传统的电影院购票管理系统存在诸多不便&#xff0c;如购票流程繁琐、排队时间长、无法提前选座等问题&#xff0c;给观众的观影体验带…

计算机毕业设计之:微信小程序的校园闲置物品交易平台(源码+文档+讲解)

博主介绍&#xff1a; ✌我是阿龙&#xff0c;一名专注于Java技术领域的程序员&#xff0c;全网拥有10W粉丝。作为CSDN特邀作者、博客专家、新星计划导师&#xff0c;我在计算机毕业设计开发方面积累了丰富的经验。同时&#xff0c;我也是掘金、华为云、阿里云、InfoQ等平台…

计算机毕业设计 校园新闻管理系统的设计与实现 Java实战项目 附源码+文档+视频讲解

博主介绍&#xff1a;✌从事软件开发10年之余&#xff0c;专注于Java技术领域、Python人工智能及数据挖掘、小程序项目开发和Android项目开发等。CSDN、掘金、华为云、InfoQ、阿里云等平台优质作者✌ &#x1f345;文末获取源码联系&#x1f345; &#x1f447;&#x1f3fb; 精…

隐匿发案:David律所代理艺术家Ina Tomecek的两张青蛙版权画维权

案件基本情况&#xff1a;起诉时间&#xff1a;2024-8-14案件号&#xff1a;2024-cv-07196原告&#xff1a;Ina Tomecek原告律所&#xff1a;Law Office of David Gulbransen起诉地&#xff1a;伊利诺伊州北部法院涉案商标/版权&#xff1a;原告品牌简介&#xff1a;Ina Tomece…

Qanything 2 0源码解析系列4 图片解析逻辑

Qanything 2.0源码解析系列4: 图片解析逻辑 文章转载自&#xff1a;https://www.feifeixu.top/article/8bb8401b-9689-453f-ab86-e3ecae414e12 &#x1f600; 前言&#xff1a; 这篇文章介绍Qanything针对图片类型文件的处理逻辑 qanything_kernel/core/retriever/general_doc…

FreeMarker 禁止自动转义标签-noautoesc

&#x1f496;简介 FreeMarker 是一个用 Java 语言编写的模板引擎&#xff0c;它被设计用来生成文本输出&#xff08;HTML 网页、电子邮件、配置文件等&#xff09;。在 FreeMarker 中&#xff0c;默认情况下&#xff0c;当你在模板中输出变量时&#xff0c;如果这些变量包含 …

shardingjdbc介绍

文章目录 1、shardingjdbc介绍1.1、读写分离、数据分片&#xff08;分库分表&#xff09;中间件&#xff1a;1.1.1、shardingsphere1.1.2、mycat 2、shardingjdbc-demo搭建2.1、创建项目2.2、添加依赖2.3、application.yml2.4、创建实体类 User2.5、创建 UserMapper2.6、创建测…

DNA亲和纯化测序(DAP-seq)、组蛋白甲基化修饰(H3K4me3 ChlP-seq)

&#x1f31f; 教授团队领衔&#xff0c;全方位服务&#xff01; &#x1f680; 从实验设计到论文发表&#xff0c;一站式解决方案&#xff01; &#x1f4c8; 选择我们&#xff0c;加速您的科研进程&#xff0c;让成果不再等待&#xff01; &#x1f4dd; 专业分析 定制服…

19_Python中的上下文管理器

Python中的上下文管理器 在Python中&#xff0c;上下文管理器&#xff08;Context Manager&#xff09;是一种用于资源管理的技术&#xff0c;它可以确保资源在使用后被正确释放&#xff0c;例如文件、网络连接或锁。 上下文管理器&#xff08;Context Manager&#xff09;是…

GB28181语音对讲协议详解

GB28181-2016语音对讲流程如下图1所示&#xff1a; 图1.语音对讲流程。 其中, 信令 1 、2 、 3 、 4 为语音广播通知、 语音广播应答消息流程; 信令 5 、 1 2 、 1 3 、 1 4 、 1 5 、 1 6 为 S I P 服务器接收到客户端的呼叫请求通过 B 2 B UA 代理方式建立语音流接收者与媒…

计算机毕业设计之:基于微信小程序的电费缴费系统(源码+文档+讲解)

博主介绍&#xff1a; ✌我是阿龙&#xff0c;一名专注于Java技术领域的程序员&#xff0c;全网拥有10W粉丝。作为CSDN特邀作者、博客专家、新星计划导师&#xff0c;我在计算机毕业设计开发方面积累了丰富的经验。同时&#xff0c;我也是掘金、华为云、阿里云、InfoQ等平台…

MatrixOne助力一道创新打造高性能智能制造AIOT系统

客户简介 深圳一道创新&#xff08;ETAO Innovation&#xff09;成立于2012年&#xff0c;是一家创新型软件及信息技术服务商&#xff0c;致力于制造戏份行业—电子制造业的数字转型服务&#xff0c;构建万物互联的智能工程。一道创新致力于把先进的软件系统、数字平台、人工智…

QT中添加资源文件

什么是资源文件 项目中经常需要添加图片、‌音频、‌视频、翻译文件等文件&#xff0c;在QT中&#xff0c;这些文件会放在 .qrc 文件中来被使用。 .qrc 文件是一个XML格式的资源集合描述文件&#xff0c;是Qt中用于定义和管理资源的关键文件 如何使用 创建资源文件 在你的Qt项…