当前位置: 首页 > news >正文

ruskal 最小生成树算法

 https://www.lanqiao.cn/problems/17138/learning/

并查集+ruskal 最小生成树算法

Kruskal 算法是一种用于在加权无向连通图中寻找最小生成树(MST)的经典算法。其核心思想是基于贪心策略,通过按边权从小到大排序并逐步选择边,确保最终形成的树满足以下条件:

  1. 包含图中所有顶点(即生成树)。
  2. 边权之和最小(即最小性)。
  3. 不形成环路(确保是树结构)。

算法步骤

排序边:将图中所有边按权值从小到大排序。

初始化并查集:每个顶点初始时属于独立的集合,用于检测环路。

遍历选边:依次遍历排序后的边,若当前边的两个顶点不属于同一集合,则选择这条边加入最小生成树,并将两个顶点的集合合并;若属于同一集合(选边会形成环路),则跳过这条边。

终止条件:当选取的边数达到 顶点数 - 1 时,算法终止,此时已得到最小生成树。

关键数据结构:并查集(Union-Find)

作用:高效判断两个顶点是否连通(属于同一集合),并快速合并集合,确保算法时间复杂度为 O(E log E)(E 为边数)。

查找(Find):确定顶点所在的集合根节点。

合并(merge):将两个不同集合合并为一个集合。

package lanqiao;import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;public class Main {static int[] union;public static void main(String[] args) {// TODO Auto-generated method stubScanner scan=new Scanner(System.in);int n=scan.nextInt();int m=scan.nextInt();List<int[]> list=new ArrayList();for(int i=0;i<m;i++) {int[] arr=new int[3];arr[0]=scan.nextInt();arr[1]=scan.nextInt();arr[2]=scan.nextInt();list.add(arr);}//并查集初始化union=new int[n+1];for(int i=1;i<=n;i++) {union[i]=i;}//Kruskal 最小生成树算法list.sort(((a,b)->a[2]-b[2]));int edgs=0;int max=Integer.MIN_VALUE;for(int[] arr:list) {int x=find(arr[0]);int y=find(arr[1]);if(x!=y) {edgs++;max=Math.max(max, arr[2]);merge(arr[0],arr[1]);}// 如果已经添加了n-1条边,说明已经得到了最小生成树,输出最大边权并结束程序if(edgs==n-1) {System.out.println(max);return;}}System.out.println(-1);}//查找public static int find(int x) {if(x!=union[x]) {union[x]=find(union[x]);  //路径压缩优化,使在递归过程中,//直接把arr[x]变为根结点,从而减少下一次查询的时间}return union[x];}//合并public static void merge(int x,int y) {x=find(x);y=find(y);if(x!=y) {union[x]=union[y];  //把y的根结点变成x的根结点}}}

相关文章:

ruskal 最小生成树算法

https://www.lanqiao.cn/problems/17138/learning/ 并查集ruskal 最小生成树算法 Kruskal 算法是一种用于在加权无向连通图中寻找最小生成树&#xff08;MST&#xff09;的经典算法。其核心思想是基于贪心策略&#xff0c;通过按边权从小到大排序并逐步选择边&#xff0c;确保…...

多系统环境下,如何构建高效的主数据管理体系?

企业信息化建设步伐不断加快&#xff0c;各类业务系统如雨后春笋般涌现&#xff0c;如ERP、CRM、SCM、MES等等。然而&#xff0c;系统繁多也带来了一个棘手的问题&#xff1a;数据孤岛。各系统间数据标准不一、信息不流通、口径不统一&#xff0c;导致企业主数据&#xff08;如…...

Linux515 rsync定时备份

凌晨1时三分进行备份 源码 code: code指定文件夹定时备份rsync到备份机指定文件夹 一.环境配置(code,backup&#xff09; 1.关闭防火墙 设置selinux相关为0 setenforce 0 /etc/selinux/config SELINUXdisable 分别配置 2.设置主机名 3.配置ip地址&#xff08;…...

Claude官方63组提示词模板全解析:从工作到生活的AI应用指南

在当今AI技术飞速发展的时代&#xff0c;大模型如ChatGPT、Claude等已成为我们工作和生活中不可或缺的助手。然而&#xff0c;许多用户发现同样的AI工具在不同人手中能产生截然不同的效果——关键在于提示词(Prompt)的质量。 提示词是与AI沟通的桥梁&#xff0c;好的提示词能…...

C#中的typeof操作符与Type类型:揭秘.NET反射的基础

引言 在C#编程中&#xff0c;反射&#xff08;Reflection&#xff09;是一种强大的机制&#xff0c;它允许我们在运行时检查和操作类型、方法、属性等程序元素。而这种反射能力的核心就是typeof操作符和System.Type类。当我们希望动态加载程序集、创建对象实例、调用方法&…...

鸿蒙OSUniApp 实现的表单验证与提交功能#三方框架 #Uniapp

UniApp 实现的表单验证与提交功能 前言 在移动端应用开发中&#xff0c;表单是用户与应用交互的重要媒介。一个好的表单不仅布局合理、使用方便&#xff0c;还应该具备完善的验证与提交功能&#xff0c;以确保用户输入的数据准确无误。本文将分享如何在 UniApp 中实现表单验证…...

开源的跨语言GUI元素理解8B大模型:AgentCPM-GUI

一、模型概述 AgentCPM-GUI 是由清华大学自然语言处理实验室 (THUNLP) 和 ModelBest 联合开发的开源大模型。该模型基于 MiniCPM-V 架构&#xff0c;拥有 80 亿参数规模&#xff0c;是一个能够直接在终端设备上运行的轻量化智能体。它创新性地将多模态输入与 GUI 操作相结合&a…...

Function Calling

在介绍Function Calling之前我们先了解一个概念,接口。 接口 两种常见接口: 人机交互接口,User Interface,简称 UI应用程序编程接口,Application Programming Interface,简称 API接口能「通」的关键,是两边都要遵守约定。 人要按照 UI 的设计来操作。UI 的设计要符合人…...

星巴克中国要卖在高点

9%能否救70%的急&#xff1f; 作者|古廿 编辑|文昌龙 星巴克中国刚刚回暖&#xff0c;总部出售的计划再次提上日程。 5月15日&#xff0c;外媒又适时放出消息&#xff1a;星巴克将开始出售其在中国的股份。消息人士称&#xff0c;星巴克本周通过一位财务顾问向几位潜在投资…...

Docker实现MySQL数据库主从复制

一、拉取数据库镜像 docker pull mysql:5.7二、创建两个数据库(一主一从模式) mysql01&#xff08;主&#xff09; 1.docker run -d -p 3310:3306 -v /root/mysql/node-1/init:/docker-entrypoinit-initdb.d -v /root/mysql/node-1/config:/etc/mysql/conf.d -v /root/mysq…...

【物联网】基于树莓派的物联网开发【4】——WIFI+SSH远程登录树莓派

使用背景 没有有线网络&#xff0c;无屏幕如何远程登录&#xff1f;程序猫教大家如何通过电脑wifi热点的方式连接树莓派&#xff0c;ssh连接访问树莓派&#xff0c;包括putty开源远程工具进行连接&#xff0c;VNC远程桌面显示。 注&#xff1a;新手建议买一个树莓派配置的显示…...

CentOS7 OpenSSL升级1.1.1w

1.安装依赖 # openssl-3.4.0需要perl-IPC-Cmd perl-Data-Dumper yum -y install gcc* yum -y install perl-IPC-Cmd perl-Data-Dumper 2.备份、卸载旧OpenSSL 查找安装目录并备份 # whereis openssl openssl: /usr/bin/openssl /usr/lib64/openssl /usr/share/man/man1/op…...

高精度降压稳压技术在现代工业自动化中的应用

一、引言 在现代工业自动化的浪潮中&#xff0c;电源管理技术犹如隐藏在精密机械背后的智囊&#xff0c;虽不直接参与生产流程的逻辑决策&#xff0c;却是保障各类自动化设备稳定、高效运行的基石。高精度降压稳压技术&#xff0c;作为电源管理领域的核心分支&#xff0c;聚焦…...

鸿蒙OSUniApp制作动态筛选功能的列表组件(鸿蒙系统适配版)#三方框架 #Uniapp

使用UniApp制作动态筛选功能的列表组件&#xff08;鸿蒙系统适配版&#xff09; 前言 随着移动应用的普及&#xff0c;用户对应用内容检索和筛选的需求也越来越高。在开发跨平台应用时&#xff0c;动态筛选功能已成为提升用户体验的重要组成部分。本文将详细介绍如何使用UniA…...

Qt中控件的Viewport作用

在Qt中&#xff0c;viewport是控件中用于显示内容的一个概念区域&#xff0c;它在可滚动控件中尤为重要。以下是viewport的主要作用和特点&#xff1a; 主要作用 内容显示区域&#xff1a;viewport定义了控件中实际可见的部分&#xff0c;所有内容都在这个区域内显示。 滚动机…...

论文学习_Precise and Accurate Patch Presence Test for Binaries

摘要&#xff1a;打补丁是应对软件漏洞的主要手段&#xff0c;及时将补丁应用到所有受影响的软件上至关重要&#xff0c;然而这一点在实际中常常难以做到&#xff0c;研究背景。因此&#xff0c;准确检测安全补丁是否已被集成进软件发行版本的能力&#xff0c;对于防御者和攻击…...

ubuntu服务器版启动卡在start job is running for wait for...to be Configured

目录 前言 一、原因分析 二、解决方法 总结 前言 当 Ubuntu 服务器启动时&#xff0c;系统会显示类似 “start job is running for wait for Network to be Configured” 或 “start job is running for wait for Plymouth Boot Screen Service” 等提示信息&#xff0c;并且…...

国产数据库工具突围:SQLynx如何解决Navicat的三大痛点?深度体验报告

引言&#xff1a;Navicat的"中国困境" 当开发者面对达梦数据库的存储过程调试&#xff0c;或是在人大金仓中处理复杂查询时&#xff0c;Navicat突然变得力不从心——这不是个例。 真实痛点&#xff1a;某政务系统迁移至OceanBase后&#xff0c;开发团队发现Navicat无…...

牛客网NC21994:分钟计算

牛客网NC21994&#xff1a;分钟计算 &#x1f4dd; 题目描述 输入格式 输入两行&#xff0c;每行包含两个整数&#xff0c;分别表示小时和分钟第一行表示起始时间&#xff0c;第二行表示结束时间 输出格式 输出一个整数&#xff0c;表示两个时间点之间的分钟数 示例 输入…...

全球宠物经济新周期下的亚马逊跨境采购策略革新——宠物用品赛道成本优化三维路径

在全球"孤独经济"与"银发经济"双轮驱动下&#xff0c;宠物用品市场正经历结构性增长。Euromonitor数据显示&#xff0c;2023年全球市场规模突破1520亿美元&#xff0c;其中中国供应链贡献度达38%&#xff0c;跨境电商出口增速连续三年超25%。在亚马逊流量红…...

Tomcat多应用部署与静态资源路径问题全解指南

&#x1f9d1; 博主简介&#xff1a;CSDN博客专家、CSDN平台优质创作者&#xff0c;高级开发工程师&#xff0c;数学专业&#xff0c;10年以上C/C, C#, Java等多种编程语言开发经验&#xff0c;拥有高级工程师证书&#xff1b;擅长C/C、C#等开发语言&#xff0c;熟悉Java常用开…...

128.在 Vue 3 中使用 OpenLayers 实现绘制矩形截图并保存地图区域

&#x1f4cc; 本文将介绍如何在 Vue 3 中使用 OpenLayers 实现&#xff1a; 1&#xff09;用户可在地图上绘制矩形&#xff1b; 2&#xff09;自动截取该区域地图为图片&#xff1b; 3&#xff09;一键保存为本地 PNG 图片。 ✨效果如下图所示 &#x1f9e0;一、前言 在地图类…...

使用 163 邮箱实现 Spring Boot 邮箱验证码登录

使用 163 邮箱实现 Spring Boot 邮箱验证码登录 本文将详细介绍如何使用网易 163 邮箱作为 SMTP 邮件服务器&#xff0c;实现 Spring Boot 项目中的邮件验证码发送功能&#xff0c;并解决常见配置报错问题。 一、为什么需要邮箱授权码&#xff1f; 出于安全考虑&#xff0c;大…...

python处理异常,JSON

异常处理 #异常处理 # 在连接MySQL数据库的过程中&#xff0c;如果不能有效地处理异常&#xff0c;则异常信息过于复杂&#xff0c;对用户不友好&#xff0c;暴露过多的敏感信息 # 所以&#xff0c;在真实的生产环境中&#xff0c; 程序必须有效地处理和控制异常&#xff0c;按…...

原生微信小程序 textarea组件placeholder无法换行的问题解决办法

【问题描述】 微信小程序原生代码&#xff0c;使用文本域&#xff0c;placeholder使用\n 没有效果&#xff0c;网上找了一堆方案说使用 也没有效果 最后在一个前端大佬博客&#xff0c;找到解决办法&#xff0c;CSS设置word-wrap: break-word; white-space: pre-line; 【解决办…...

毕设设计 | 管理系统图例

文章目录 环素1. 登录、注册2. 菜单管理 环素 1. 登录、注册 2. 菜单管理 公告通知 订单管理 会员管理 奖品管理 新增、编辑模块...

激光雷达视觉定位是3D视觉定位吗?

激光雷达视觉定位通常被归类为3D视觉定位&#xff0c;但具体来说&#xff0c;它是融合了激光雷达&#xff08;LiDAR&#xff09;数据和视觉&#xff08;图像&#xff09;数据的多模态3D定位方法。我们可以从几个角度来理解这点&#xff1a; 为什么说它属于3D视觉定位&#xff…...

每周靶点:NY-ESO-1、GPC3、IL27分享

本期精选了《自身免疫性癌抗原NY-ESO-1》《肝细胞癌标记物GPC3》《白细胞介素IL27》三篇文章。以下为各研究内容的概述&#xff1a; 自身免疫性癌抗原NY-ESO-1 NY-ESO-1是一种自身免疫性癌抗原&#xff0c;也称为CTA1B&#xff08;CTAG1B&#xff09;&#xff0c;由主要组织相…...

Maven 插件参数注入与Mojo开发详解

&#x1f9d1; 博主简介&#xff1a;CSDN博客专家&#xff0c;历代文学网&#xff08;PC端可以访问&#xff1a;https://literature.sinhy.com/#/?__c1000&#xff0c;移动端可微信小程序搜索“历代文学”&#xff09;总架构师&#xff0c;15年工作经验&#xff0c;精通Java编…...

Java详解RabbitMQ工作模式之发布订阅模式

目录 一、发布订阅模式简介二、发布订阅模式的工作原理2.1 核心组件2.2 工作流程 三、代码示例3.1 生产者代码3.2 消费者代码 四、实际应用场景五、注意事项六、总结 在分布式系统中&#xff0c;消息队列作为异步通信的桥梁&#xff0c;扮演着至关重要的角色。而 RabbitMQ&…...

UR5e机器人Matlab仿真

在 MATLAB 中使用 UR5e 机器人模型进行仿真和控制&#xff0c;通常需要结合机器人系统工具箱&#xff08;Robotics System Toolbox&#xff09; UR5e loadrobot("universalUR5e","DataFormat","column"); UR5e.Gravity [0 0 -9.81]; % 保存机器…...

[ctfshow web入门] web75

信息收集 scandir被禁用了 解题 cforeach(new DirectoryIterator("glob:///*") as $a){echo($a->__toString(). ); } ob_flush();cif ( $a opendir("glob:///*") ) {while ( ($file readdir($a)) ! false ) {echo $file."<br>";}c…...

论文中表格跨页该怎么整(如何给跨页表格添加标题和表头)

标题&#xff1a;光标移动到第一行表格&#xff0c;然后快捷键;ctrl shirft enter&#xff0c;就会发现第二页多了一行&#xff0c;再把标题复制张贴过来即可 表头&#xff1a; 光标移动到第一行表格&#xff0c;鼠标右键 选择插入 再选择在上方插入行&#xff0c;然后手动添加…...

day26 Python 自定义函数

目录 一、函数的基本定义 示例 1&#xff1a;不带参数的函数 示例 2&#xff1a;查看文档字符串 二、带参数的函数 示例 3&#xff1a;带一个参数的函数 示例 4&#xff1a;带多个参数的函数 三、带返回值的函数 示例 5&#xff1a;计算两个数的和并返回结果 示例 6&am…...

洛谷P4907题解

题目传送门 题意&#xff1a; 扑克牌的部分牌被移除&#xff0c;需从剩牌中选 4 个区间&#xff0c;每个区间的牌都是同一花色且点数连续。如果不可选&#xff0c;输出最少需添加几张牌才能满足要求。 思路&#xff1a; 暴力和剪枝。 暴力&#xff1a;按照题意模拟&#xff…...

【MyBatis插件】PageHelper 分页

前言 在开发 Web 应用时&#xff0c;我们经常需要处理海量数据的展示问题。例如&#xff0c;在一个电商平台上&#xff0c;商品列表可能有成千上万条数据。如果我们一次性将所有数据返回给前端&#xff0c;不仅会导致页面加载缓慢&#xff0c;还会对数据库造成巨大压力。为了解…...

AI数字人融合VR全景:从技术突破到可信场景落地

摘要 本文深度解析AI数字人与VR全景技术融合的技术架构&#xff0c;结合故宫博物院、西门子、强生等真实行业案例&#xff0c;揭示技术落地的关键路径与量化价值。通过具体技术参数、实施细节及权威机构数据&#xff0c;构建可信的技术应用图景&#xff0c;为开发者提供可复用…...

机器学习——朴素贝叶斯练习题

一、 使用鸢尾花数据训练多项式朴素贝叶斯模型&#xff0c;并评估模型 代码展示&#xff1a; from sklearn.datasets import load_iris from sklearn.metrics import accuracy_score from sklearn.model_selection import train_test_split from sklearn.naive_bayes impor…...

【爬虫】DrissionPage-3

安装&#xff1a;4.1最新版本 pip install drissionpage --upgrade 官方文档&#xff1a;&#x1f6f0;️ 连接浏览器 | DrissionPage官网 1 Chromium对象 Chromium对象用于连接和管理浏览器。标签页的开关和获取、整体运行参数配置、浏览器信息获取等都由它进行。 1.1 默认…...

网络爬虫学习之httpx的使用

开篇 本文整理自《Python3 网络爬虫实战》&#xff0c;主要是httpx的使用。 笔记整理 使用urllib库requests库的使用&#xff0c;已经可以爬取绝大多数网站的数据&#xff0c;但对于某些网站依然无能为力。 这是因为这些网站强制使用HTTP/2.0协议访问&#xff0c;这时urllib和r…...

TASK02【Datawhale 组队学习】使用 LLM API 开发应用

文章目录 system prompt 和 user prompt高效prompt&#xff1a;用清晰、详尽的语言表达 Prompt原则一&#xff1a;清晰&#xff0c;具体的指令分隔符寻求结构化的输出要求模型检查是否满足条件提供少量示例 "Few-shot" prompting 原则二&#xff0c;给模型时间去思考…...

黑马k8s(七)

1.Pod介绍 查看版本&#xff1a; 查看类型,这里加s跟不加s没啥区别&#xff0c;可加可不加 2.Pod基本配置 3.镜像拉去策略 本地没有这个镜像&#xff0c;策略是Never&#xff0c;启动失败 查看拉去策略&#xff1a; 更改拉去策略&#xff1a; 4.启动命令 运行的是nginx、busv…...

【FMC216】基于 VITA57.1 的 2 路 TLK2711 发送、2 路 TLK2711 接收 FMC 子卡模块

产品概述 FMC216 是一款基于 VITA57.1 标准规范的 2 路 TLK2711 接收、2 路 TLK2711 发送 FMC 子卡模块。该板卡支持 2 路 TLK2711 数据的收发&#xff0c;支持线速率 1.6Gbps&#xff0c;经过 TLK2711 高速串行收发器&#xff0c;可以将 1.6Gbps 的高速串行数据解串为 16 位并…...

如何在Edge浏览器里-安装梦精灵AI提示词管理工具

方案一&#xff08;应用中心安装-推荐&#xff09;&#xff1a; 梦精灵 跨平台AI提示词管理工具 - Microsoft Edge AddonsMake Microsoft Edge your own with extensions that help you personalize the browser and be more productive.https://microsoftedge.microsoft.com…...

Ubuntu shell指定conda的python环境启动脚本

Ubuntu shell指定conda的python环境启动脚本。 通过指令&#xff0c;获取目前系统的conda虚拟python环境 conda info -e 如下图所示&#xff0c;为我自己电脑的python环境 # conda environments: # base * /home/ubuntu/miniconda3 kitti …...

深入理解无监督学习与K-means聚类算法:原理与实践

一、无监督学习概述 无监督学习(Unsupervised Learning)是机器学习的重要分支之一&#xff0c;与有监督学习不同&#xff0c;它不需要预先标记的训练数据。在无监督学习中&#xff0c;计算机仅根据样本的特征或样本间的相关性&#xff0c;从数据中自动发现隐藏的模式或结构。 …...

单片机-STM32部分:16、Git工具使用

Docshttps://x509p6c8to.feishu.cn/wiki/Pftrw3Z6niRlewkurnyctyw1nQx 使用Git管理本地仓库的好处是&#xff0c;可以知道自己每次修改了哪些内容&#xff0c;随时进行版本切换。 待完善。...

扬州卓韵酒店用品:优质洗浴用品,提升酒店满意度与品牌形象

在酒店提供的服务里&#xff0c;沐浴用品占据了非常重要的地位&#xff0c;其质量与种类直接关系到客人洗澡时的感受。好的沐浴用品能让客人洗澡时感到舒心和快乐&#xff0c;反之&#xff0c;质量不好的用品可能会影响客人整个住宿期间的愉悦心情。挑选恰当的洗浴用品不仅能够…...

Coze 实战教程 | 10 分钟打造你的AI 助手

> 文章中的 xxx 自行替换&#xff0c;文章被屏蔽了。 &#x1f4f1; 想让你的xxx具备 AI 对话能力&#xff1f;本篇将手把手教你&#xff0c;如何用 Coze 平台快速构建一个能与用户自然交流、自动回复提问的 xxx助手&#xff0c;零代码、超高效&#xff01; &#x1f4cc;…...

使用 frp 实现内网穿透:从基础到进阶

在日常开发中&#xff0c;我们经常会遇到需要将本地服务暴露给外部用户的情况&#xff0c;比如测试同学需要临时测试一个本地开发的 Web 服务&#xff0c;或者希望在出差时远程访问家里的 NAS。这些需求的核心问题都是如何实现内网穿透。 一、为什么选择 frp&#xff1f; 经过…...