【代码随想录Day53】图论Part05

server/2024/11/28 13:32:44/

并查集理论基础

题目链接/文章讲解:并查集理论基础 | 代码随想录

寻找存在的路径

题目链接/文章讲解:代码随想录

java">import java.util.*;public class Main {public static void main(String[] args) {int numberOfElements, numberOfConnections;Scanner scanner = new Scanner(System.in);// 读取元素数量和连接数量numberOfElements = scanner.nextInt();numberOfConnections = scanner.nextInt();// 初始化并查集DisjointSetUnion disjointSet = new DisjointSetUnion(numberOfElements + 1);// 读取每对连接并合并for (int i = 0; i < numberOfConnections; ++i) {int elementA = scanner.nextInt();int elementB = scanner.nextInt();disjointSet.union(elementA, elementB);}// 检查两个元素是否在同一集合中int queryElementA = scanner.nextInt();int queryElementB = scanner.nextInt();if (disjointSet.isConnected(queryElementA, queryElementB)) {System.out.println("1"); // 在同一集合} else {System.out.println("0"); // 不在同一集合}}
}// 并查集实现
class DisjointSetUnion {private int[] parent;public DisjointSetUnion(int size) {parent = new int[size];// 初始化每个元素的父节点为自己for (int i = 0; i < size; ++i) {parent[i] = i;}}// 查找元素的根节点,并进行路径压缩public int find(int element) {if (element != parent[element]) {parent[element] = find(parent[element]); // 路径压缩}return parent[element];}// 合并两个元素的集合public void union(int elementA, int elementB) {int rootA = find(elementA);int rootB = find(elementB);if (rootA != rootB) {parent[rootB] = rootA; // 将B的根节点指向A的根节点}}// 检查两个元素是否在同一集合中public boolean isConnected(int elementA, int elementB) {return find(elementA) == find(elementB);}
}

http://www.ppmy.cn/server/137707.html

相关文章

【制造业&船运】航拍交通设施与交通工具检测系统源码&数据集全套:改进yolo11-unireplknet

改进yolo11-DRBNCSPELAN等200全套创新点大全&#xff1a;航拍交通设施与交通工具检测系统源码&#xff06;数据集全套 1.图片效果展示 项目来源 人工智能促进会 2024.11.01 注意&#xff1a;由于项目一直在更新迭代&#xff0c;上面“1.图片效果展示”和“2.视频效果展示”展…

详细分析 MyBatis 参数映射与使用(附Demo)

目录 前言1. 基本知识2. Demo3. 拓展 前言 对于Java的基本知识推荐阅读&#xff1a; java框架 零基础从入门到精通的学习路线 附开源项目面经等&#xff08;超全&#xff09;【Java项目】实战CRUD的功能整理&#xff08;持续更新&#xff09; 原先写过xml的动态Sql&#xff…

[MySQL]介绍与基础指令

介绍 现在常见的数据库如:Oracle、DB 2、SQL Server、MySQL等都是关系型数据库&#xff0c;使用二维表格来存储数据。 关系结构型数据库系统 管理员 仓库 MySQL的数据存储目录为data&#xff0c;在data下的每个目录都代表一个数据库。 MySQL的安装目录下&#xff1a; bin目录…

【51单片机】矩阵键盘

学习使用的开发板&#xff1a;STC89C52RC/LE52RC 编程软件&#xff1a;Keil5 烧录软件&#xff1a;stc-isp 开发板实图&#xff1a; 文章目录 矩阵键盘 矩阵键盘 矩阵键盘位于开发板的右下角 在键盘中按键数量较多时&#xff0c;为了减少I/O口的占用&#xff0c;通常将按键…

excel IF函数用法

IF函数以其灵活多变、易于上手的特点&#xff0c;成为了众多Excel用户不可或缺的好帮手&#xff0c;无论是简单的条件判断&#xff0c;还是复杂的逻辑分析&#xff0c;IF函数都能游刃有余地应对。 本文将深入探讨IF函数的10种精妙用法&#xff0c;从基础到进阶&#xff0c;相信…

JS | CommonJS、AMD、CMD、ES6-Module、UMD五种JS模块化规范

目录 前言 一、CommonJS 模块化规范 二、ES6 模块化规范 三、AMD 模块化规范 四、CMD 模块化规范 五、UMD模块化规范 前言 这三个规范都是为Js模块化加载而生的&#xff0c;使模块能够按需加载&#xff0c;使系统同庞杂的代码得到组织和管理。模块化的管理代码使多人开发…

SYN590RH

一般描述 SYN590RH是SYNOXO全新开发设计的一款宽电压范围&#xff0c;低功耗&#xff0c;高性能&#xff0c;无需外置AGC电容&#xff0c;灵敏度达到典型-110 dBm,400MHz~450MHz频率范围应用的单芯片ASK或00 K射频接收器。 SYN590RH是一款典型的即插即用型单片高…

大数据之文件服务器方案

大数据文件服务器方案 一&#xff0c;文件服务器常用框架 二&#xff0c;文件服务器常用框架的实现技术 文件服务器常用框架 文件服务器是一种专门用于存储、管理和共享文件的服务器&#xff0c;其常用框架的实现技术涉及多个方面&#xff0c;以下是一些主要的实现技术及其详…