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技术编写坦克大战游戏,并…...
postgresql|数据库|只读用户的创建和删除(备忘)
CREATE USER read_only WITH PASSWORD 密码 -- 连接到xxx数据库 \c xxx -- 授予对xxx数据库的只读权限 GRANT CONNECT ON DATABASE xxx TO read_only; GRANT USAGE ON SCHEMA public TO read_only; GRANT SELECT ON ALL TABLES IN SCHEMA public TO read_only; GRANT EXECUTE O…...
C++中string流知识详解和示例
一、概览与类体系 C 提供三种基于内存字符串的流,定义在 <sstream> 中: std::istringstream:输入流,从已有字符串中读取并解析。std::ostringstream:输出流,向内部缓冲区写入内容,最终取…...
华为云Flexus+DeepSeek征文|DeepSeek-V3/R1 商用服务开通全流程与本地部署搭建
华为云FlexusDeepSeek征文|DeepSeek-V3/R1 商用服务开通全流程与本地部署搭建 前言 如今大模型其性能出色,华为云 ModelArts Studio_MaaS大模型即服务平台华为云内置了大模型,能助力我们轻松驾驭 DeepSeek-V3/R1,本文中将分享如何…...
Aspose.PDF 限制绕过方案:Java 字节码技术实战分享(仅供学习)
Aspose.PDF 限制绕过方案:Java 字节码技术实战分享(仅供学习) 一、Aspose.PDF 简介二、说明(⚠️仅供学习与研究使用)三、技术流程总览四、准备工作1. 下载 Jar 包2. Maven 项目依赖配置 五、字节码修改实现代码&#…...
视觉slam十四讲实践部分记录——ch2、ch3
ch2 一、使用g++编译.cpp为可执行文件并运行(P30) g++ helloSLAM.cpp ./a.out运行 二、使用cmake编译 mkdir build cd build cmake .. makeCMakeCache.txt 文件仍然指向旧的目录。这表明在源代码目录中可能还存在旧的 CMakeCache.txt 文件,或者在构建过程中仍然引用了旧的路…...
【Go语言基础【13】】函数、闭包、方法
文章目录 零、概述一、函数基础1、函数基础概念2、参数传递机制3、返回值特性3.1. 多返回值3.2. 命名返回值3.3. 错误处理 二、函数类型与高阶函数1. 函数类型定义2. 高阶函数(函数作为参数、返回值) 三、匿名函数与闭包1. 匿名函数(Lambda函…...
CSS | transition 和 transform的用处和区别
省流总结: transform用于变换/变形,transition是动画控制器 transform 用来对元素进行变形,常见的操作如下,它是立即生效的样式变形属性。 旋转 rotate(角度deg)、平移 translateX(像素px)、缩放 scale(倍数)、倾斜 skewX(角度…...
Chromium 136 编译指南 Windows篇:depot_tools 配置与源码获取(二)
引言 工欲善其事,必先利其器。在完成了 Visual Studio 2022 和 Windows SDK 的安装后,我们即将接触到 Chromium 开发生态中最核心的工具——depot_tools。这个由 Google 精心打造的工具集,就像是连接开发者与 Chromium 庞大代码库的智能桥梁…...
从面试角度回答Android中ContentProvider启动原理
Android中ContentProvider原理的面试角度解析,分为已启动和未启动两种场景: 一、ContentProvider已启动的情况 1. 核心流程 触发条件:当其他组件(如Activity、Service)通过ContentR…...
在 Spring Boot 中使用 JSP
jsp? 好多年没用了。重新整一下 还费了点时间,记录一下。 项目结构: pom: <?xml version"1.0" encoding"UTF-8"?> <project xmlns"http://maven.apache.org/POM/4.0.0" xmlns:xsi"http://ww…...
