LeetCode:1319. 连通网络的操作次数(并查集 Java)
目录
1319. 连通网络的操作次数
题目描述:
实现代码与解析:
并查集
原理思路:
1319. 连通网络的操作次数
题目描述:
用以太网线缆将 n 台计算机连接成一个网络,计算机的编号从 0 到 n-1。线缆用 connections 表示,其中 connections[i] = [a, b] 连接了计算机 a 和 b。
网络中的任何一台计算机都可以通过网络直接或者间接访问同一个网络中其他任意一台计算机。
给你这个计算机网络的初始布线 connections,你可以拔开任意两台直连计算机之间的线缆,并用它连接一对未直连的计算机。请你计算并返回使所有计算机都连通所需的最少操作次数。如果不可能,则返回 -1 。
示例 1:

输入:n = 4, connections = [[0,1],[0,2],[1,2]] 输出:1 解释:拔下计算机 1 和 2 之间的线缆,并将它插到计算机 1 和 3 上。
示例 2:

输入:n = 6, connections = [[0,1],[0,2],[0,3],[1,2],[1,3]] 输出:2
示例 3:
输入:n = 6, connections = [[0,1],[0,2],[0,3],[1,2]] 输出:-1 解释:线缆数量不足。
示例 4:
输入:n = 5, connections = [[0,1],[0,2],[3,4],[2,3]] 输出:0
提示:
1 <= n <= 10^51 <= connections.length <= min(n*(n-1)/2, 10^5)connections[i].length == 20 <= connections[i][0], connections[i][1] < nconnections[i][0] != connections[i][1]- 没有重复的连接。
- 两台计算机不会通过多条线缆连接。
实现代码与解析:
并查集
class Solution {int[] p = new int[(int)1e5 + 10];public int find(int x) {if (p[x] != x) p[x] = find(p[x]);return p[x];}public int makeConnected(int n, int[][] connections) {for (int i = 0; i < p.length; i++) {p[i] = i;}int count = 0; // 可多出来的线for (int[] t: connections) {int a = t[0];int b = t[1];if (find(a) == find(b)) {count++;continue;}p[find(a)] = find(b);}int res = 0; // 减一表示连接需要的线,不减一就是需要连接的块数for (int i = 0; i < n; i++) {if (p[i] == i) res++;}System.out.println(count);System.out.println(res);return res - 1 > count ? -1 : res - 1;}
}
原理思路:
并查集算法,不过需要稍微思考一下。
我们在合并连接时,先判断是否已经连接,若已经连接,说明此线是多出来的线。最后找出不想连的连通块的个数n,如果想要把他们全部连接,就需要n - 1条线,若多余的线大于等于n - 1,那么就可以完成全部联通,返回n - 1,若小于那么无论如何也无法联通,返回-1。
相关文章:
LeetCode:1319. 连通网络的操作次数(并查集 Java)
目录 1319. 连通网络的操作次数 题目描述: 实现代码与解析: 并查集 原理思路: 1319. 连通网络的操作次数 题目描述: 用以太网线缆将 n 台计算机连接成一个网络,计算机的编号从 0 到 n-1。线缆用 connections 表示…...
C++ STL教程
C STL教程 文章目录 C STL教程1.1 std::vector1.1.1vector的定义1.1.2vector容器的初始化1.1.3vector容器内元素的访问和修改1.1.4vector中的常用函数 1.2 std::string1.2.1string的定义1.2.2string的初始化1.2.3string中元素的访问和修改1.2.4string中连接字符串1.2.5string中…...
系列学习前端之第 6 章:一文掌握 jQuery(熟悉即可)
前言:为什么说 jQuery 熟悉即可,已日渐过时? 作为前端开发中常用的两个库或框架:Vue.js 和 jQuery。不少开发者想要学习 Vue.js 时,都会有一个疑惑:学习 Vue.js 是否一定要学习 jQuery? 从几个…...
python 中判断文件、目录是否存在的方法
判断目录是否存在并创建目录 一、实现上传文件功能二、判断目录是否存在的办法2.1、使用os模块2.1.1、判断目录是否存在2.1.2、os.makedirs():递归创建目录 2.2、使用pathlib模块2.2.1、path.exist()判断目录是否存在2.2.1、path.mkdir():创建目录 2.3、…...
Redis的安装与启动
一、Linux环境安装&启动Redis 1. 安装步骤 第一步:在官网下载好Redis安装包,上传到Linux中并进行解压到相应(如/opt/software/)目录中;(注意:完成了第二步后,即安装了C/C语言…...
WebGIS航线编辑器(无人机航线规划)
无人机航点、航线规划,实现全自动航点飞行作业及飞行航拍。禁飞区、作业区功能保障飞行安全。 GIS引擎加载 const viewer new Cesium.Viewer("cesiumContainer", { imageryProvider: new Cesium.IonImageryProvider({ assetId: 3872 }), }); const im…...
STEP 格式三维模型读取
STEP是常用的三维模型存储格式,使用Express语言描述几何图形,文件存储方式为BRep,分为STEP203和STEP214,后者多了颜色信息,opencascade中提供了相应算法读取STEP文件。 #include <STEPControl_Reader.hxx>TopoD…...
Mora: Enabling Generalist Video Generation via A Multi-Agent Framework
目录 论文地址:Mora: Enabling Generalist Video Generation viaA Multi-Agent Framework github地址:https://github.com/lichao-sun/Mora 一、摘要 (1)Mora 的主要特点: (2)Mora的应用场景…...
[c++] 自写 MyString 类
实现了 MyString 类,同时实现了运算符重载,重载的运算符包括 <、>、、!、<<、>>、[] 等。 如果一个类重载了某个运算符,那么对这个类的对象进行操作的时候便会使用类重载的运算符。比如下边代码 MyString 类中重载了 <、…...
三、阅读器开发--4、阅读器目录、全文搜索功能开发
1、阅读器目录 1.1、实现目录 先实现目录的布局 定义一个蒙版,充满整个屏幕浮在阅读器上方,左侧为目录右侧为背景,目录下方包含一个tab,点击后会切换不同的内容,这里tab是目录、书签,这里可以通过如下的…...
AMEYA360代理 | 江苏长晶科技FST2.0高性能 IGBT产品介绍
江苏长晶科技股份有限公司是一家专业从事半导体产品研发、生产和销售的企业。自2019年起,连续4年被中国半导体行业协会评为 “功率器件十强企业”。2021年开始自主研发有着“工业CPU”之称的IGBT,截至2023年Q3在家电/工业/新能源等行业实现8款产品市场应…...
基于springboot+vue+Mysql的网上图书商城
开发语言:Java框架:springbootJDK版本:JDK1.8服务器:tomcat7数据库:mysql 5.7(一定要5.7版本)数据库工具:Navicat11开发软件:eclipse/myeclipse/ideaMaven包:…...
阿里云服务器多少钱一个月?低至5元1个月
阿里云服务器一个月多少钱?最便宜5元1个月。阿里云轻量应用服务器2核2G3M配置61元一年,折合5元一个月,2核4G服务器30元3个月,2核2G3M带宽服务器99元12个月,轻量应用服务器2核4G4M带宽165元12个月,4核16G服务…...
LeetCode第五天(442. 数组中重复的数据)
给你一个长度为 n 的整数数组 nums ,其中 nums 的所有整数都在范围 [1, n] 内,且每个整数出现 一次 或 两次 。请你找出所有出现 两次 的整数,并以数组形式返回。 你必须设计并实现一个时间复杂度为 O(n) 且仅使用常量额外空间的算法解决此问…...
chatgpt正面案例合集
现在可以用百度 百度安全验证 chatgpt用来搜索软件使用指令太牛了_个人渣记录仅为自己搜索用的博客-CSDN博客 chatgpt 使用案例 根据不同的目标群体变更文案和表达_个人渣记录仅为自己搜索用的博客-CSDN博客 倾听能力 和哪些基础能力相关 ,如何提高 chatgpt_个人渣记录仅为自…...
今日讲讲路由配置
下载安装路由 1. 下载安装路由库 npm i vue-router 2. 在 src 中新建 views 文件夹,在其中新建页面 3. 在 src 中新建一个 router 文件夹,其中新建一个 index.js import { createRouter, createWebHashHistory } from vue-router; // 导入页面 imp…...
【Rust】Shared-State Concurrency
Shared-State Concurrency channel类似于single ownership. 而shared memory类似与multiple ownership. multiple ownership是难于管理的. smarter pointer也是multiple ownership的. Rust的type system和ownership rules帮助实现正确的multiple ownership管理。 Using Mute…...
连接数据库(MySQL)的JDBC
目录 JDBC简介快速入门API详解DriverManager(驱动管理类)注册驱动:获取数据库连接(对象): Connection(数据库连接对象)获取执行SQL的对象管理事务 Statement(执行SQL语句)执行DML、DDL语句执行DQL语句 Resu…...
golang通过参数控制HTTP server是否使用基本认证
之前写的《golang实现一个BasicAuth的HTTP server》一定会做基本认证。 本例给出了如何通过启动时候指定的参数来控制是否做基本认证 代码对比和解释 给出与上一篇中源码的diff adminhpc-1:~/go/auth_http$ diff -ruN http_rpc_server.go_bak http_rpc_server.go --- http_rp…...
javaSwing坦克大战游戏
在游戏开发领域,坦克大战是一款经典的游戏,其简单而又耐玩的玩法吸引了无数玩家。而今,在Java编程技术的支持下,我们可以用Java Swing技术轻松实现这款经典游戏。本文将介绍如何使用Java Swing技术编写坦克大战游戏,并…...
SpringBoot-17-MyBatis动态SQL标签之常用标签
文章目录 1 代码1.1 实体User.java1.2 接口UserMapper.java1.3 映射UserMapper.xml1.3.1 标签if1.3.2 标签if和where1.3.3 标签choose和when和otherwise1.4 UserController.java2 常用动态SQL标签2.1 标签set2.1.1 UserMapper.java2.1.2 UserMapper.xml2.1.3 UserController.ja…...
Appium+python自动化(十六)- ADB命令
简介 Android 调试桥(adb)是多种用途的工具,该工具可以帮助你你管理设备或模拟器 的状态。 adb ( Android Debug Bridge)是一个通用命令行工具,其允许您与模拟器实例或连接的 Android 设备进行通信。它可为各种设备操作提供便利,如安装和调试…...
mongodb源码分析session执行handleRequest命令find过程
mongo/transport/service_state_machine.cpp已经分析startSession创建ASIOSession过程,并且验证connection是否超过限制ASIOSession和connection是循环接受客户端命令,把数据流转换成Message,状态转变流程是:State::Created 》 St…...
使用分级同态加密防御梯度泄漏
抽象 联邦学习 (FL) 支持跨分布式客户端进行协作模型训练,而无需共享原始数据,这使其成为在互联和自动驾驶汽车 (CAV) 等领域保护隐私的机器学习的一种很有前途的方法。然而,最近的研究表明&…...
视频字幕质量评估的大规模细粒度基准
大家读完觉得有帮助记得关注和点赞!!! 摘要 视频字幕在文本到视频生成任务中起着至关重要的作用,因为它们的质量直接影响所生成视频的语义连贯性和视觉保真度。尽管大型视觉-语言模型(VLMs)在字幕生成方面…...
三体问题详解
从物理学角度,三体问题之所以不稳定,是因为三个天体在万有引力作用下相互作用,形成一个非线性耦合系统。我们可以从牛顿经典力学出发,列出具体的运动方程,并说明为何这个系统本质上是混沌的,无法得到一般解…...
Axios请求超时重发机制
Axios 超时重新请求实现方案 在 Axios 中实现超时重新请求可以通过以下几种方式: 1. 使用拦截器实现自动重试 import axios from axios;// 创建axios实例 const instance axios.create();// 设置超时时间 instance.defaults.timeout 5000;// 最大重试次数 cons…...
ardupilot 开发环境eclipse 中import 缺少C++
目录 文章目录 目录摘要1.修复过程摘要 本节主要解决ardupilot 开发环境eclipse 中import 缺少C++,无法导入ardupilot代码,会引起查看不方便的问题。如下图所示 1.修复过程 0.安装ubuntu 软件中自带的eclipse 1.打开eclipse—Help—install new software 2.在 Work with中…...
OpenLayers 分屏对比(地图联动)
注:当前使用的是 ol 5.3.0 版本,天地图使用的key请到天地图官网申请,并替换为自己的key 地图分屏对比在WebGIS开发中是很常见的功能,和卷帘图层不一样的是,分屏对比是在各个地图中添加相同或者不同的图层进行对比查看。…...
AI+无人机如何守护濒危物种?YOLOv8实现95%精准识别
【导读】 野生动物监测在理解和保护生态系统中发挥着至关重要的作用。然而,传统的野生动物观察方法往往耗时耗力、成本高昂且范围有限。无人机的出现为野生动物监测提供了有前景的替代方案,能够实现大范围覆盖并远程采集数据。尽管具备这些优势…...
