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技术编写坦克大战游戏,并…...
Python|GIF 解析与构建(5):手搓截屏和帧率控制
目录 Python|GIF 解析与构建(5):手搓截屏和帧率控制 一、引言 二、技术实现:手搓截屏模块 2.1 核心原理 2.2 代码解析:ScreenshotData类 2.2.1 截图函数:capture_screen 三、技术实现&…...
深度学习在微纳光子学中的应用
深度学习在微纳光子学中的主要应用方向 深度学习与微纳光子学的结合主要集中在以下几个方向: 逆向设计 通过神经网络快速预测微纳结构的光学响应,替代传统耗时的数值模拟方法。例如设计超表面、光子晶体等结构。 特征提取与优化 从复杂的光学数据中自…...
label-studio的使用教程(导入本地路径)
文章目录 1. 准备环境2. 脚本启动2.1 Windows2.2 Linux 3. 安装label-studio机器学习后端3.1 pip安装(推荐)3.2 GitHub仓库安装 4. 后端配置4.1 yolo环境4.2 引入后端模型4.3 修改脚本4.4 启动后端 5. 标注工程5.1 创建工程5.2 配置图片路径5.3 配置工程类型标签5.4 配置模型5.…...
大话软工笔记—需求分析概述
需求分析,就是要对需求调研收集到的资料信息逐个地进行拆分、研究,从大量的不确定“需求”中确定出哪些需求最终要转换为确定的“功能需求”。 需求分析的作用非常重要,后续设计的依据主要来自于需求分析的成果,包括: 项目的目的…...
渗透实战PortSwigger靶场-XSS Lab 14:大多数标签和属性被阻止
<script>标签被拦截 我们需要把全部可用的 tag 和 event 进行暴力破解 XSS cheat sheet: https://portswigger.net/web-security/cross-site-scripting/cheat-sheet 通过爆破发现body可以用 再把全部 events 放进去爆破 这些 event 全部可用 <body onres…...
家政维修平台实战20:权限设计
目录 1 获取工人信息2 搭建工人入口3 权限判断总结 目前我们已经搭建好了基础的用户体系,主要是分成几个表,用户表我们是记录用户的基础信息,包括手机、昵称、头像。而工人和员工各有各的表。那么就有一个问题,不同的角色…...
Java-41 深入浅出 Spring - 声明式事务的支持 事务配置 XML模式 XML+注解模式
点一下关注吧!!!非常感谢!!持续更新!!! 🚀 AI篇持续更新中!(长期更新) 目前2025年06月05日更新到: AI炼丹日志-28 - Aud…...
ios苹果系统,js 滑动屏幕、锚定无效
现象:window.addEventListener监听touch无效,划不动屏幕,但是代码逻辑都有执行到。 scrollIntoView也无效。 原因:这是因为 iOS 的触摸事件处理机制和 touch-action: none 的设置有关。ios有太多得交互动作,从而会影响…...
C++八股 —— 单例模式
文章目录 1. 基本概念2. 设计要点3. 实现方式4. 详解懒汉模式 1. 基本概念 线程安全(Thread Safety) 线程安全是指在多线程环境下,某个函数、类或代码片段能够被多个线程同时调用时,仍能保证数据的一致性和逻辑的正确性…...
Spring数据访问模块设计
前面我们已经完成了IoC和web模块的设计,聪明的码友立马就知道了,该到数据访问模块了,要不就这俩玩个6啊,查库势在必行,至此,它来了。 一、核心设计理念 1、痛点在哪 应用离不开数据(数据库、No…...
