并查集题目
并查集题目
- 聚合一块(蓝桥)
- 合根植物(蓝桥)
- 等式方程的可满足性
- 省份数量
并查集(Union-Find)算法是一个专门针对「动态连通性」的算法。双方向的连通。
模板:
class UF {// 连通分量个数private int count;// 存储每个节点的父节点private int[] parent;// n 为图中节点的个数public UF(int n) {this.count = n;parent = new int[n];for (int i = 0; i < n; i++) {parent[i] = i;}}// 将节点 p 和节点 q 连通public void union(int p, int q) {int rootP = find(p);int rootQ = find(q);if (rootP == rootQ)return;parent[rootQ] = rootP;// 两个连通分量合并成一个连通分量count--;}// 判断节点 p 和节点 q 是否连通public boolean connected(int p, int q) {int rootP = find(p);int rootQ = find(q);return rootP == rootQ;}public int find(int x) {if (parent[x] != x) {parent[x] = find(parent[x]);}return parent[x];}// 返回图中的连通分量个数public int count() {return count;}
}
聚合一块(蓝桥)

import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改public class Main{public static void main(String[] args) {Scanner scan = new Scanner(System.in);//在此输入您的代码...int n=scan.nextInt();int m=scan.nextInt();UF uf=new UF(n+1);for(int i=0;i<m;i++){int q=scan.nextInt();int p=scan.nextInt();uf.union(q,p);}System.out.println(uf.count-2);scan.close();}
}
class UF{//连通分量个数int count;//存储每个节点的父节点int[]parent;//创建n个节点的连通图UF(int n){this.count=n;parent=new int[n];for(int i=1;i<n;i++){parent[i]=i;}}//将p和q联通void union(int p,int q){int rootP=find(p);int rootQ=find(q);if(rootP==rootQ){return;}parent[rootQ]=rootP;count--;}int find(int x){if(parent[x]!=x){parent[x]=find(parent[x]);}return parent[x];}int count(){return count;}
}
合根植物(蓝桥)
题目

import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改public class Main {public static void main(String[] args) {Scanner scan = new Scanner(System.in);//在此输入您的代码...int m=scan.nextInt();int n=scan.nextInt();UF uf=new UF(m*n+1);int k=scan.nextInt();for(int i=0;i<k;i++){int a=scan.nextInt();int b=scan.nextInt();uf.union(a,b);}System.out.println(uf.count-1);scan.close();}
}
class UF{int count;int[] parent;UF(int n){this.count=n;parent=new int[n];for(int i=1;i<n;i++){parent[i]=i;}}int find(int x){if(parent[x]!=x){parent[x]=find(parent[x]);}return parent[x];}void union(int q,int p){int rootQ=find(q);int rootP=find(p);if(rootP==rootQ){return;}parent[rootP]=rootQ;count--;}
}
等式方程的可满足性
题目

思路:先执行“= =”的式子, 连通“==”两边的字母。后来执行“! =”的式子,判断“! =”两边的字母是否连通,如果连通就返回false。
class Solution {public boolean equationsPossible(String[] equations) {UF uf=new UF(26);//先排一下序,使先执行“==”,!的ASCLL较小,输出从大到小,后-前Arrays.sort(equations, new Comparator<String>() {@Overridepublic int compare(String o1, String o2) {return o2.charAt(1)-o1.charAt(1);}});for(String ele:equations){int q=ele.charAt(0)-'a';int p=ele.charAt(3)-'a';if(ele.charAt(1)=='='){//连通q puf.union(q,p);}else{if(uf.isConnected(q,p)){return false;}}}return true;}
}
class UF{int count;int[]parent;UF(int n){this.count=n;parent=new int[n];for(int i=0;i<n;i++){parent[i]=i;}}void union(int q,int p){int rootQ=find(q);int rootP=find(p);if(rootP==rootQ){return;}parent[rootP]=rootQ;count--;}boolean isConnected(int q,int p){int rootQ=find(q);int rootP=find(p);return rootP==rootQ;}int find(int x){if(x!=parent[x]){parent[x]=find(parent[x]);}return parent[x];}
}
省份数量
题目

class Solution {public int findCircleNum(int[][] isConnected) {int size=isConnected.length;UF uf=new UF(size);for(int i=0;i<size;i++){for(int j=i+1;j<size;j++){if(isConnected[i][j]==1){uf.union(i,j);}}}return uf.count;}
}class UF {// 连通分量个数int count;// 存储每个节点的父节点private int[] parent;// n 为图中节点的个数public UF(int n) {this.count = n;parent = new int[n];for (int i = 0; i < n; i++) {parent[i] = i;}}// 将节点 p 和节点 q 连通public void union(int p, int q) {int rootP = find(p);int rootQ = find(q);if (rootP == rootQ)return;parent[rootQ] = rootP;// 两个连通分量合并成一个连通分量count--;}// 判断节点 p 和节点 q 是否连通public boolean connected(int p, int q) {int rootP = find(p);int rootQ = find(q);return rootP == rootQ;}public int find(int x) {if (parent[x] != x) {parent[x] = find(parent[x]);}return parent[x];}// 返回图中的连通分量个数public int count() {return count;}
}
相关文章:
并查集题目
并查集题目 聚合一块(蓝桥)合根植物(蓝桥)等式方程的可满足性省份数量 并查集(Union-Find)算法是一个专门针对「动态连通性」的算法。双方向的连通。 模板: class UF {// 连通分量个数private …...
日志2025.2.9
日志2025.2.9 1.增加了敌人挥砍类型 2.增加了敌人的死亡状态 在敌人身上添加Ragdoll,死后激活布偶模式 public class EnemyRagdoll : MonoBehaviour { private Rigidbody[] rigidbodies; private Collider[] colliders; private void Awake() { rigidbodi…...
支持多种网络数据库格式的自动化转换工具——VisualXML
一、VisualXML软件介绍 对于DBC、ARXML……文件的编辑、修改等繁琐操作,WINDHILL风丘科技开发的总线设计工具——VisualXML,可轻松解决这一问题,提升工作效率。 VisualXML是一个强大且基于Excel表格生成多种网络数据库文件的转换工具&#…...
Java并发编程笔记
Java并发基础知识补全 启动 启动线程的方式只有: 1、X extends Thread;,然后X.start 2、X implements Runnable;然后交给Thread运行 线程的状态 Java中线程的状态分为6种: 1. 初始(NEW):新创建了一个线程对象&…...
大语言模型实践——基于现有API的二次开发
基于现有的API平台做一些实用的AI小应用。 API服务商:阿里云百炼 云服务器:阿里云(2核2GB) 部署框架:gradio 调用框架:openai 语言:Python (注:若搭建网站或API接口…...
获取程序运行目录 (jar运行目录)
FileSystems.getDefault().getPath("").toAbsolutePath().toString() 和 Path.get(MyClass.class.getProtectionDomain().getCodeSource().getLocation().toURI()).getParent() 这两个代码片段在Java中用于获取不同的路径,尤其在打包为JAR文件运行时会有显…...
Elasticsearch:如何使用 Elastic 检测恶意浏览器扩展
作者:来着 Elastic Aaron Jewitt 当你的 CISO 询问你的任何工作站上是否安装过特定的浏览器扩展时,你多快能得到正确答案?恶意浏览器扩展是一个重大威胁,许多组织无法管理或检测。这篇博文探讨了 Elastic Infosec 团队如何使用 os…...
Oracle CDB自动处理表空间不足脚本
之前我曾经发过一个自动处理表空间的脚本,可以通过定时任务自动处理表空间不足的问题;但是之前那个脚本没有涵盖CDB模式下的PDB,这里将脚本做了一下更新,可以处理CDB模式下多PDB的表空间问题。 传统模式的脚本请参考这个链接 Or…...
java-list深入理解(流程图)
List源码学习: 此篇文章使用流程图和源码方式,理解List的源码,方便记忆 核心逻辑流程图: #mermaid-svg-BBrPrDuqUdLMtHvj {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-BBrPrDuqUdLMtHvj .error-icon{fill:#…...
Vue 中的 keep-alive 组件是什么?
Vue 中的 keep-alive 组件 keep-alive 是 Vue.js 提供的一个内置组件,用于在组件切换时缓存组件的状态。它可以有效提高用户体验,特别是在需要频繁切换视图的场景中,例如在 SPA(单页面应用)中。 目录 什么是 keep-alive如何使用 keep-alive属性介绍实际示例注意事项总结…...
单元测试的入门实践与应用
单元测试的目的是验证代码中最小的可测试单元(通常为函数或方法)是否按预期运行。它应当独立于系统的其他部分,并专注于特定的功能。 在软件开发中,单元测试是确保代码质量与可维护性的核心环节。优秀的单元测试不仅能帮助开发者…...
【大模型】硅基流动对接DeepSeek使用详解
目录 一、前言 二、硅基流动介绍 2.1 硅基流动平台介绍 2.1.1 平台是做什么的 2.2 主要特点与功能 2.2.1 适用场景 三、硅基流动快速使用 3.1 账户注册 3.2 token获取 3.2.1 获取token技巧 四、Cherry-Studio对接DeepSeek 4.1 获取 Cherry-Studio 4.2 Cherry-Stud…...
[Windows] PDF补丁丁v1.1.0.4627绿色版
[Windows] PDF补丁丁 链接:https://pan.xunlei.com/s/VOIdp50MV2BkOrFott_SCev1A1?pwdvbw4# PDFPatcher 是一款专门用于编辑 PDF 文件的软件,其主要功能包括添加、删除、修改、替换和提取 PDF 文件中的文本、图像、页面等内容,以及支持密码…...
Oracle 变更redo log文件位置
更改Oracle数据库的Redo log文件位置,可以按照以下步骤操作。 1.查询当前Redo log文件信息 select * from v$log; select * from v$logfile;通过查询结果可知Redo log文件放在/oradata/redofile 目录下。 2.拷贝redo log文件到新的位置/Data/redolog $cd /orada…...
使用Redis实现业务信息缓存(缓存详解,缓存更新策略,缓存三大问题)
一、什么是缓存? 缓存是一种高效的数据存储方式,它通过将数据保存在内存中来提供快速的读写访问。这种机制特别适用于需要高速数据访问的应用场景,如网站、应用程序和服务。在处理大量数据和高并发请求时, 缓存能显著提高性能和用户体验。 Redis就是一款常用的缓存中间件。…...
已验证正常,Java输入字符串生成PDF文件
Java输入字符串生成PDF文件过程: 在Java开发中,如何将字符串转换为 PDF 是一个常见的需求。网上找了很多例子都无法生成,经过多次尝试,终于实现了,特此记录一下。 1、引入pom.xml 添加所需的依赖 <dependency>&…...
android手机安装deepseek-r1:1.5b
序 本文主要展示一下如何在android手机上安装deepseek-r1:1.5b 步骤 安装termux 到https://termux.dev/cn/index.html去下载 然后执行termux-setup-storage以获取手机存储权限 安装构建依赖 pkg install git cmake golang下载ollama git clone --depth 1 https://gitee.…...
51单片机俄罗斯方块清屏函数
/************************************************************************************************************** * 名称:LED_Clr * 功能:清屏 * 参数:NULL * 返回:NULL * 备注:temp数组为动态显示数据ÿ…...
PLSQL: 存储过程,用户自定义函数[oracle]
注意: raise notice是高斯的输出语句; DBMS_OUT_PUT.PUT_LINE是oracle的输出语句 存储过程 Stored Procedure 存储过程可以封装数据访问逻辑,使得应用程序可以通过调用存储过程来执行这些逻辑,而不是直接执行SQL语句。这有助于提高代码的可重用性、可…...
深度学习-医学影像诊断
以下以使用深度学习进行医学影像(如 X 光片)的肺炎诊断为例,为你展示基于 PyTorch 框架的代码实现。我们将构建一个简单的卷积神经网络(CNN)模型,使用公开的肺炎 X 光影像数据集进行训练和评估。 1. 安装必…...
Leetcode 3576. Transform Array to All Equal Elements
Leetcode 3576. Transform Array to All Equal Elements 1. 解题思路2. 代码实现 题目链接:3576. Transform Array to All Equal Elements 1. 解题思路 这一题思路上就是分别考察一下是否能将其转化为全1或者全-1数组即可。 至于每一种情况是否可以达到…...
基于距离变化能量开销动态调整的WSN低功耗拓扑控制开销算法matlab仿真
目录 1.程序功能描述 2.测试软件版本以及运行结果展示 3.核心程序 4.算法仿真参数 5.算法理论概述 6.参考文献 7.完整程序 1.程序功能描述 通过动态调整节点通信的能量开销,平衡网络负载,延长WSN生命周期。具体通过建立基于距离的能量消耗模型&am…...
MongoDB学习和应用(高效的非关系型数据库)
一丶 MongoDB简介 对于社交类软件的功能,我们需要对它的功能特点进行分析: 数据量会随着用户数增大而增大读多写少价值较低非好友看不到其动态信息地理位置的查询… 针对以上特点进行分析各大存储工具: mysql:关系型数据库&am…...
解决Ubuntu22.04 VMware失败的问题 ubuntu入门之二十八
现象1 打开VMware失败 Ubuntu升级之后打开VMware上报需要安装vmmon和vmnet,点击确认后如下提示 最终上报fail 解决方法 内核升级导致,需要在新内核下重新下载编译安装 查看版本 $ vmware -v VMware Workstation 17.5.1 build-23298084$ lsb_release…...
微信小程序 - 手机震动
一、界面 <button type"primary" bindtap"shortVibrate">短震动</button> <button type"primary" bindtap"longVibrate">长震动</button> 二、js逻辑代码 注:文档 https://developers.weixin.qq…...
DeepSeek 技术赋能无人农场协同作业:用 AI 重构农田管理 “神经网”
目录 一、引言二、DeepSeek 技术大揭秘2.1 核心架构解析2.2 关键技术剖析 三、智能农业无人农场协同作业现状3.1 发展现状概述3.2 协同作业模式介绍 四、DeepSeek 的 “农场奇妙游”4.1 数据处理与分析4.2 作物生长监测与预测4.3 病虫害防治4.4 农机协同作业调度 五、实际案例大…...
使用 SymPy 进行向量和矩阵的高级操作
在科学计算和工程领域,向量和矩阵操作是解决问题的核心技能之一。Python 的 SymPy 库提供了强大的符号计算功能,能够高效地处理向量和矩阵的各种操作。本文将深入探讨如何使用 SymPy 进行向量和矩阵的创建、合并以及维度拓展等操作,并通过具体…...
C# 求圆面积的程序(Program to find area of a circle)
给定半径r,求圆的面积。圆的面积应精确到小数点后5位。 例子: 输入:r 5 输出:78.53982 解释:由于面积 PI * r * r 3.14159265358979323846 * 5 * 5 78.53982,因为我们只保留小数点后 5 位数字。 输…...
CSS设置元素的宽度根据其内容自动调整
width: fit-content 是 CSS 中的一个属性值,用于设置元素的宽度根据其内容自动调整,确保宽度刚好容纳内容而不会超出。 效果对比 默认情况(width: auto): 块级元素(如 <div>)会占满父容器…...
初探Service服务发现机制
1.Service简介 Service是将运行在一组Pod上的应用程序发布为网络服务的抽象方法。 主要功能:服务发现和负载均衡。 Service类型的包括ClusterIP类型、NodePort类型、LoadBalancer类型、ExternalName类型 2.Endpoints简介 Endpoints是一种Kubernetes资源…...
