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

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^5
  • 1 <= connections.length <= min(n*(n-1)/2, 10^5)
  • connections[i].length == 2
  • 0 <= connections[i][0], connections[i][1] < n
  • connections[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. 连通网络的操作次数 题目描述&#xff1a; 实现代码与解析&#xff1a; 并查集 原理思路&#xff1a; 1319. 连通网络的操作次数 题目描述&#xff1a; 用以太网线缆将 n 台计算机连接成一个网络&#xff0c;计算机的编号从 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(熟悉即可)

前言&#xff1a;为什么说 jQuery 熟悉即可&#xff0c;已日渐过时&#xff1f; 作为前端开发中常用的两个库或框架&#xff1a;Vue.js 和 jQuery。不少开发者想要学习 Vue.js 时&#xff0c;都会有一个疑惑&#xff1a;学习 Vue.js 是否一定要学习 jQuery&#xff1f; 从几个…...

python 中判断文件、目录是否存在的方法

判断目录是否存在并创建目录 一、实现上传文件功能二、判断目录是否存在的办法2.1、使用os模块2.1.1、判断目录是否存在2.1.2、os.makedirs()&#xff1a;递归创建目录 2.2、使用pathlib模块2.2.1、path.exist()判断目录是否存在2.2.1、path.mkdir()&#xff1a;创建目录 2.3、…...

Redis的安装与启动

一、Linux环境安装&启动Redis 1. 安装步骤 第一步&#xff1a;在官网下载好Redis安装包&#xff0c;上传到Linux中并进行解压到相应&#xff08;如/opt/software/&#xff09;目录中&#xff1b;&#xff08;注意&#xff1a;完成了第二步后&#xff0c;即安装了C/C语言…...

WebGIS航线编辑器(无人机航线规划)

无人机航点、航线规划&#xff0c;实现全自动航点飞行作业及飞行航拍。禁飞区、作业区功能保障飞行安全。 GIS引擎加载 const viewer new Cesium.Viewer("cesiumContainer", { imageryProvider: new Cesium.IonImageryProvider({ assetId: 3872 }), }); const im…...

STEP 格式三维模型读取

STEP是常用的三维模型存储格式&#xff0c;使用Express语言描述几何图形&#xff0c;文件存储方式为BRep&#xff0c;分为STEP203和STEP214&#xff0c;后者多了颜色信息&#xff0c;opencascade中提供了相应算法读取STEP文件。 #include <STEPControl_Reader.hxx>TopoD…...

Mora: Enabling Generalist Video Generation via A Multi-Agent Framework

目录 论文地址&#xff1a;Mora: Enabling Generalist Video Generation viaA Multi-Agent Framework github地址&#xff1a;https://github.com/lichao-sun/Mora 一、摘要 &#xff08;1&#xff09;Mora 的主要特点&#xff1a; &#xff08;2&#xff09;Mora的应用场景…...

[c++] 自写 MyString 类

实现了 MyString 类&#xff0c;同时实现了运算符重载&#xff0c;重载的运算符包括 <、>、、!、<<、>>、[] 等。 如果一个类重载了某个运算符&#xff0c;那么对这个类的对象进行操作的时候便会使用类重载的运算符。比如下边代码 MyString 类中重载了 <、…...

三、阅读器开发--4、阅读器目录、全文搜索功能开发

1、阅读器目录 1.1、实现目录 先实现目录的布局 定义一个蒙版&#xff0c;充满整个屏幕浮在阅读器上方&#xff0c;左侧为目录右侧为背景&#xff0c;目录下方包含一个tab&#xff0c;点击后会切换不同的内容&#xff0c;这里tab是目录、书签&#xff0c;这里可以通过如下的…...

AMEYA360代理 | 江苏长晶科技FST2.0高性能 IGBT产品介绍

江苏长晶科技股份有限公司是一家专业从事半导体产品研发、生产和销售的企业。自2019年起&#xff0c;连续4年被中国半导体行业协会评为 “功率器件十强企业”。2021年开始自主研发有着“工业CPU”之称的IGBT&#xff0c;截至2023年Q3在家电/工业/新能源等行业实现8款产品市场应…...

基于springboot+vue+Mysql的网上图书商城

开发语言&#xff1a;Java框架&#xff1a;springbootJDK版本&#xff1a;JDK1.8服务器&#xff1a;tomcat7数据库&#xff1a;mysql 5.7&#xff08;一定要5.7版本&#xff09;数据库工具&#xff1a;Navicat11开发软件&#xff1a;eclipse/myeclipse/ideaMaven包&#xff1a;…...

阿里云服务器多少钱一个月?低至5元1个月

阿里云服务器一个月多少钱&#xff1f;最便宜5元1个月。阿里云轻量应用服务器2核2G3M配置61元一年&#xff0c;折合5元一个月&#xff0c;2核4G服务器30元3个月&#xff0c;2核2G3M带宽服务器99元12个月&#xff0c;轻量应用服务器2核4G4M带宽165元12个月&#xff0c;4核16G服务…...

LeetCode第五天(442. 数组中重复的数据)

给你一个长度为 n 的整数数组 nums &#xff0c;其中 nums 的所有整数都在范围 [1, n] 内&#xff0c;且每个整数出现 一次 或 两次 。请你找出所有出现 两次 的整数&#xff0c;并以数组形式返回。 你必须设计并实现一个时间复杂度为 O(n) 且仅使用常量额外空间的算法解决此问…...

chatgpt正面案例合集

现在可以用百度 百度安全验证 chatgpt用来搜索软件使用指令太牛了_个人渣记录仅为自己搜索用的博客-CSDN博客 chatgpt 使用案例 根据不同的目标群体变更文案和表达_个人渣记录仅为自己搜索用的博客-CSDN博客 倾听能力 和哪些基础能力相关 ,如何提高 chatgpt_个人渣记录仅为自…...

今日讲讲路由配置

下载安装路由 1. 下载安装路由库 npm i vue-router 2. 在 src 中新建 views 文件夹&#xff0c;在其中新建页面 3. 在 src 中新建一个 router 文件夹&#xff0c;其中新建一个 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&#xff08;驱动管理类&#xff09;注册驱动&#xff1a;获取数据库连接(对象)&#xff1a; Connection&#xff08;数据库连接对象&#xff09;获取执行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坦克大战游戏

在游戏开发领域&#xff0c;坦克大战是一款经典的游戏&#xff0c;其简单而又耐玩的玩法吸引了无数玩家。而今&#xff0c;在Java编程技术的支持下&#xff0c;我们可以用Java Swing技术轻松实现这款经典游戏。本文将介绍如何使用Java Swing技术编写坦克大战游戏&#xff0c;并…...

vscode里如何用git

打开vs终端执行如下&#xff1a; 1 初始化 Git 仓库&#xff08;如果尚未初始化&#xff09; git init 2 添加文件到 Git 仓库 git add . 3 使用 git commit 命令来提交你的更改。确保在提交时加上一个有用的消息。 git commit -m "备注信息" 4 …...

多模态2025:技术路线“神仙打架”,视频生成冲上云霄

文&#xff5c;魏琳华 编&#xff5c;王一粟 一场大会&#xff0c;聚集了中国多模态大模型的“半壁江山”。 智源大会2025为期两天的论坛中&#xff0c;汇集了学界、创业公司和大厂等三方的热门选手&#xff0c;关于多模态的集中讨论达到了前所未有的热度。其中&#xff0c;…...

基于距离变化能量开销动态调整的WSN低功耗拓扑控制开销算法matlab仿真

目录 1.程序功能描述 2.测试软件版本以及运行结果展示 3.核心程序 4.算法仿真参数 5.算法理论概述 6.参考文献 7.完整程序 1.程序功能描述 通过动态调整节点通信的能量开销&#xff0c;平衡网络负载&#xff0c;延长WSN生命周期。具体通过建立基于距离的能量消耗模型&am…...

新能源汽车智慧充电桩管理方案:新能源充电桩散热问题及消防安全监管方案

随着新能源汽车的快速普及&#xff0c;充电桩作为核心配套设施&#xff0c;其安全性与可靠性备受关注。然而&#xff0c;在高温、高负荷运行环境下&#xff0c;充电桩的散热问题与消防安全隐患日益凸显&#xff0c;成为制约行业发展的关键瓶颈。 如何通过智慧化管理手段优化散…...

docker 部署发现spring.profiles.active 问题

报错&#xff1a; org.springframework.boot.context.config.InvalidConfigDataPropertyException: Property spring.profiles.active imported from location class path resource [application-test.yml] is invalid in a profile specific resource [origin: class path re…...

JAVA后端开发——多租户

数据隔离是多租户系统中的核心概念&#xff0c;确保一个租户&#xff08;在这个系统中可能是一个公司或一个独立的客户&#xff09;的数据对其他租户是不可见的。在 RuoYi 框架&#xff08;您当前项目所使用的基础框架&#xff09;中&#xff0c;这通常是通过在数据表中增加一个…...

STM32HAL库USART源代码解析及应用

STM32HAL库USART源代码解析 前言STM32CubeIDE配置串口USART和UART的选择使用模式参数设置GPIO配置DMA配置中断配置硬件流控制使能生成代码解析和使用方法串口初始化__UART_HandleTypeDef结构体浅析HAL库代码实际使用方法使用轮询方式发送使用轮询方式接收使用中断方式发送使用中…...

并发编程 - go版

1.并发编程基础概念 进程和线程 A. 进程是程序在操作系统中的一次执行过程&#xff0c;系统进行资源分配和调度的一个独立单位。B. 线程是进程的一个执行实体,是CPU调度和分派的基本单位,它是比进程更小的能独立运行的基本单位。C.一个进程可以创建和撤销多个线程;同一个进程中…...

【 java 虚拟机知识 第一篇 】

目录 1.内存模型 1.1.JVM内存模型的介绍 1.2.堆和栈的区别 1.3.栈的存储细节 1.4.堆的部分 1.5.程序计数器的作用 1.6.方法区的内容 1.7.字符串池 1.8.引用类型 1.9.内存泄漏与内存溢出 1.10.会出现内存溢出的结构 1.内存模型 1.1.JVM内存模型的介绍 内存模型主要分…...

给网站添加live2d看板娘

给网站添加live2d看板娘 参考文献&#xff1a; stevenjoezhang/live2d-widget: 把萌萌哒的看板娘抱回家 (ノ≧∇≦)ノ | Live2D widget for web platformEikanya/Live2d-model: Live2d model collectionzenghongtu/live2d-model-assets 前言 网站环境如下&#xff0c;文章也主…...