【代码随想录Day53】图论Part05

news/2024/11/2 9:35:09/

并查集理论基础

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

寻找存在的路径

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

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/news/1543829.html

相关文章

一些MATLAB到Python的转换指南

1. 矩阵和数组操作 MATLAB使用方括号[]来创建矩阵和数组。Python使用列表[]或NumPy库中的数组。 MATLAB: A [1 2 3; 4 5 6; 7 8 9];Python: import numpy as npA np.array([[1, 2, 3], [4, 5, 6], [7, 8, 9]])2. 数学运算 MATLAB中很多内置函数可以直接用于矩阵。Python…

T级别DDoS攻击与大型DDoS防御

在数字化高速发展的今天&#xff0c;网络攻击和安全防御的博弈愈加复杂&#xff0c;分布式拒绝服务&#xff08;DDoS&#xff09;攻击已然成为网络安全领域的一大难题。尤其是达到T级别的DDoS攻击&#xff0c;以每秒TB级别&#xff08;Tbps&#xff09;的超高流量给网络系统带来…

使用Navicat连接远程服务器中在docker中运行的MySQL数据库保姆级教程

使用Navicat连接远程服务器中在docker中运行的MySQL数据库保姆级教程 一、需要的资源 Navicat客户端&#xff08;我使用的是17.0.8版本&#xff0c;安装教程B站搜一个&#xff0c;很快能解决&#xff09;服务器&#xff08;已安装docker并运行了MySQL&#xff09; 二、步骤 …

uniapp使用echart

一 直线图 三中国地图 <template><view class"content"><l-echart ref"chartRef"></l-echart></view> </template><script setup> import { ref, onMounted } from "vue"; import geoJson from &quo…

clickhouse运维篇(二):多机器手动部署ck集群

熟悉流程并且有真正部署需求可以看一下我的另一篇简化部署的文章&#xff0c;因为多节点配置还是比较麻烦的先要jdk、zookeeper&#xff0c;再ck&#xff0c;还有各种配置文件登录不同机器上手动改配置文件还挺容易出错的。 clickhouse运维篇&#xff08;三&#xff09;&#x…

PCB电源层布线信号

在印刷电路板(PCB)的设计过程中,电源层通常被视为电源分配网络(PDN)的核心。电源层和接地层通常是通过平面铜层来实现的,旨在确保系统稳定性。然而,随着电路板复杂性的增加,尤其是在多层电路板中,设计师可能面临在电源层上布置信号线路的需求。虽然这种做法可以节省空…

LabVIEW在Windows和Linux开发的差异

LabVIEW广泛应用于工程和科研领域的自动化和测量控制系统开发&#xff0c;其在Windows和Linux平台上的开发环境有所不同。这些差异主要体现在操作系统兼容性、硬件支持、软件库和驱动程序、实时系统开发以及部署选择上。以下从各个方面详细对比分析LabVIEW在Windows与Linux系统…

Flink(一)

目录 架构处理有界与无界数据部署应用到任意地方运行任意规模应用利用内存性能 流应用流处理应用的基本组件流状态时间 应用场景事件驱动应用事件驱动应用的优势Flink如何支持事件驱动应用&#xff1f; 典型的事件驱动示例 数据分析应用流式分析应用的优势&#xff1f;Flink 如…