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

代码随想录算法训练营第六十二天 | 108. 冗余连接、109. 冗余连接II、复习

108. 冗余连接

题目链接:https://kamacoder.com/problempage.php?pid=1181
文档讲解:https://www.programmercarl.com/kamacoder/0108.%E5%86%97%E4%BD%99%E8%BF…

思路

从前向后遍历每一条边(因为优先让前面的边连上),边的两个节点如果不在同一个集合,就加入集合(即:同一个根节点)。如果边的两个节点已经出现在同一个集合里,说明着边的两个节点已经连在一起了,再加入这条边一定就出现环了。然后直接输出。

代码

import java.util.*;class Main {static int[] father;static int n;public static void main (String[] args) {Scanner in = new Scanner(System.in);n = in.nextInt();father = new int[n + 1];init();for (int i = 0; i < n; i++) {int a = in.nextInt();int b = in.nextInt();if (isSame(a, b)) {System.out.println(a + " " + b);return;} else {join(a, b);}}}public static void init() {for (int i = 1; i <= n; i++) father[i] = i;}public static int find (int u) {return u == father[u] ? u : (father[u] = find(father[u]));}public static boolean isSame(int u, int v) {return find(u) == find(v);}public static void join(int u, int v) {u = find(u);v = find(v);if (u == v) return ;father[v] = u;}
}

109. 冗余连接II

题目链接:https://kamacoder.com/problempage.php?pid=1182
文档讲解:https://www.programmercarl.com/kamacoder/0109.%E5%86%97%E4%BD%99%E8%BF…

思路

有向树的性质,如果是有向树的话,只有根节点入度为0,其他节点入度都为1。

  • 情况一:如果我们找到入度为2的点,那么删一条指向该节点的边就行了。
  • 情况二:入度为2 还有一种情况,只能删特定的一条边。
  • 情况三: 如果没有入度为2的点,说明图中有环了。

用数组把每条边记录下来,并统计节点入度,如果存在入度为2的节点,则实现函数isTreeAfterRemoveEdge(),否则实现函数getRemoveEdge()

  • isTreeAfterRemoveEdge()判断删一个边之后是不是有向树: 将所有边的两端节点分别加入并查集,遇到要删除的边则跳过,如果遇到即将加入并查集的边的两端节点本来就在并查集了,说明构成了环。如果顺利将所有边的两端节点(除了要删除的边)加入了并查集,则说明删除该条边是一个有向树。
  • getRemoveEdge()确定图中一定有了有向环,那么要找到需要删除的那条边: 将所有边的两端节点分别加入并查集,如果遇到即将加入并查集的边的两端节点 本来就在并查集了,说明构成了环。

代码

import java.util.*;
class Main {static int[] father, inDegree, vec;static int[][] edges;static int n;public static void main (String[] args) {Scanner in = new Scanner(System.in);n = in.nextInt();inDegree = new int[n + 1];vec = new int[2]; // 保存edges中对应边的行数father = new int[n + 1];edges = new int[n][2];for (int i = 0; i < n; i++) {edges[i][0] = in.nextInt();edges[i][1] = in.nextInt();inDegree[edges[i][1]]++;}int j = 0;for (int i = n - 1; i >= 0; i--) {if (inDegree[edges[i][1]] == 2) {vec[j++] = i;}}if (j > 0) {if (isTreeAfterRemoveEdge(vec[0])) {// 如果移掉这条边后是树,则输出System.out.println(edges[vec[0]][0] + " " + edges[vec[0]][1]);} else {System.out.println(edges[vec[1]][0] + " " + edges[vec[1]][1]);}return;}getRemoveEdge();}public static void init() {for (int i = 1; i <= n; i++) father[i] = i;}public static int find(int u) {return u == father[u] ? u : (father[u] = find(father[u]));}public static boolean isSame(int u, int v) {return find(u) == find(v);}public static void join(int u, int v) {u = find(u);v = find(v);if (u == v) return;father[v] = u;}public static boolean isTreeAfterRemoveEdge(int index) {init();for (int i = 0; i < n; i++) {if (i == index) continue;if (isSame(edges[i][0], edges[i][1])) return false;else join(edges[i][0], edges[i][1]);}return true;}public static void getRemoveEdge() {init();for (int i = 0; i < n; i++) {if (isSame(edges[i][0], edges[i][1])) {System.out.println(edges[i][0] + " " + edges[i][1]);return;} else join(edges[i][0], edges[i][1]);}}
}

老是忘记初始化并查集。

相关文章:

代码随想录算法训练营第六十二天 | 108. 冗余连接、109. 冗余连接II、复习

108. 冗余连接 题目链接&#xff1a;https://kamacoder.com/problempage.php?pid1181 文档讲解&#xff1a;https://www.programmercarl.com/kamacoder/0108.%E5%86%97%E4%BD%99%E8%BF… 思路 从前向后遍历每一条边&#xff08;因为优先让前面的边连上&#xff09;&#xff0…...

昇思MindSpore学习笔记6-01LLM原理和实践--FCN图像语义分割

摘要&#xff1a; 记录MindSpore AI框架使用FCN全卷积网络理解图像进行图像语议分割的过程、步骤和方法。包括环境准备、下载数据集、数据集加载和预处理、构建网络、训练准备、模型训练、模型评估、模型推理等。 一、概念 1.语义分割 图像语义分割 semantic segmentation …...

【FFMPEG基础(一)】解码源码

学习分享 main函数decodetorgb32.h 文件decodetorgb32 .cpp文件 main函数 #include <QApplication> #include "decodetorgb32.h" int main(int argc, char *argv[]) {QApplication a(argc, argv);DecodeToRGB32 toRGB32;int restoRGB32.openVideo("../fi…...

第二证券股市资讯:深夜!突然暴涨75%!

一则重磅收买引发医药圈轰动。 北京时间7月8日晚间&#xff0c;美股开盘后&#xff0c;美国生物制药公司Morphic股价一度暴升超75%。音讯面上&#xff0c;生物医药巨子礼来公司官宣&#xff0c;将以57美元/股的价格现金收买Morphic&#xff0c;较上星期五的收盘价溢价79%&…...

flutter 使用wechat_assets_picker的权限检测

https://pub.dev/packages/wechat_assets_picker AssetPicker.pickAssets之前进行权限检查 pickImages() async {try {if (PermissionState.authorized ! await AssetPicker.permissionCheck()) {PermissionUtil.showAllPermissions(Permission.storage, 1);return;}final Lis…...

Mojo入门案例教程(上手篇)

以下是 Mojo 编程语言入门案例教程&#xff0c;内容包括 Mojo 的基本概念、变量、控制结构、函数等方面&#xff1a; Mojo 的基本概念 1.什么是 Mojo&#xff1f;&#xff1a;Mojo 是一种函数式编程语言&#xff0c;用于开发小型应用程序、脚本和工具。 2.Mojo 的特点&#x…...

如何在window执行mkfile

1、Windows cmd中出现错误&#xff1a;“‘make‘ 不是内部或外部命令&#xff0c;也不是可运行的程序或批处理文件。”的解决方法_windows_是板栗啊-GitCode 开源社区 2、安装cmder&#xff0c;再通过包管理工具下载make...

Nginx 是一个非常流行的 Web 服务器和反向代理服务器

Nginx 是一个非常流行的 Web 服务器和反向代理服务器&#xff0c;以其高性能、稳定性、丰富的功能集和低资源消耗而闻名。下面是一个简化的 Nginx 使用教程&#xff0c;包括基本的安装、配置和一些常见用途。 安装 Nginx 在 Ubuntu/Debian 上安装&#xff1a; sudo apt upda…...

mysql怎么调整缓冲区大小

MySQL中调整缓冲区大小是数据库性能优化的重要一环。缓冲区大小直接影响了数据库的读写性能和响应速度。以下是一些常见的MySQL缓冲区及其调整方法&#xff1a; 一、InnoDB缓冲池&#xff08;InnoDB Buffer Pool&#xff09; InnoDB缓冲池是InnoDB存储引擎用来缓存表数据和索…...

计算机组成原理学习笔记(一)

计算机组成原理 [类型:: [[计算机基础课程]] ] [来源:: [[B站]] ] [主讲人:: [[咸鱼学长]] ] [评价:: ] [知识点:: [[系统软件]] & [[应用软件]] ] [简单解释:: 管理计算机系统的软件&#xff1b; 按照任务需要编写的程序 ] [问题:: ] [知识点:: [[机器字长]] ] [简单…...

Vue3 对跳转 同一路由传入不同参数的页面分别进行缓存

1&#xff1a;使用场景 从列表页跳转至不同的详情页面&#xff0c;对这些详情页面分别进行缓存 2&#xff1a;核心代码 2.1: 配置路由文件 在路由文件里对需要进行缓存的路由对象添加meta 属性 // 需要缓存的详情页面路由 { name: detail, path: /myRouter/detail…...

LinearLayout的测量流程

在日常开发中我们常常使用LinearLayout作为布局Group&#xff0c;本文从其源码实现出发分析测量流程。大家可以带着问题进入下面的分析流程&#xff0c;看看是否能找到答案。 垂直测量 View的测量入口方法是onmeasure方法。LinearLayout的onMeasure方法根据其方向而做不同的处…...

数据无忧:Ubuntu 系统迁移备份全指南

唠唠闲话 最近电脑出现了一些故障&#xff0c;送修期间&#xff0c;不得不在实验室的台式机上重装系统&#xff0c;配环境的过程花费了不少时间。为避免未来处理类似事情时耗费时间&#xff0c;特此整理一些备份策略。 先做以下准备&#xff1a; U盘启动盘&#xff0c;参考 …...

中国IDC圈探访北京•光子1号金融算力中心

今天&#xff0c;“AI”、“大模型”是最炙手可热的话题&#xff0c;全球有海量人群在工作生活中使用大模型&#xff0c;大模型产品涉及多模态&#xff0c;应用范围已涵盖电商、传媒、金融、短视频、制造等众多行业。 而回看2003年的互联网记忆&#xff0c; “上网”“在线”是…...

[Unity入门01] Unity基本操作

参考的傅老师的教程学了一下Unity的基础操作&#xff1a; [傅老師/Unity教學] Unity3D基礎入門 [華梵大學] 遊戲引擎應用基礎(Unity版本) Class#01 移动&#xff1a;鼠标中键旋转&#xff1a;鼠标右键放大&#xff1a;鼠标滚轮飞行模式&#xff1a;右键WASDQEFocus模式&…...

vivado DELAY_VALUE_XPHY、DIFF_TERM

延迟_值_XPHY PORT对象上的DELAY_VALUE_XPHY属性指定要添加的延迟量 Versal XPHY逻辑接口的输入或输出路径。在的早期阶段 opt_design在重新生成高级I/O向导IP时 DELAY_VALUE_XPHY值将从PORT复制到的XPHY实例上 输入或输出路径。Vivado设计套件中存在DRCs&#xff0c;以确保 DE…...

C++语言相关的常见面试题目(三)

1. List底层实现原理 省流&#xff1a; list底层实现了一个双向循环链表。 每个元素&#xff08;或节点&#xff09;包含三个部分&#xff1a;数据域(_M_Storage)、前驱指针(_M_prev)、后继指针(_M_next)。 数据域&#xff1a;存储实际数据。 前驱指针&#xff1a;指向链表中…...

代码随想录-Day53

739. 每日温度 给定一个整数数组 temperatures &#xff0c;表示每天的温度&#xff0c;返回一个数组 answer &#xff0c;其中 answer[i] 是指对于第 i 天&#xff0c;下一个更高温度出现在几天后。如果气温在这之后都不会升高&#xff0c;请在该位置用 0 来代替。 示例 1: …...

Android 如何通过代码实时设置EditTextView光标

背景&#xff1a;换肤框架下&#xff0c;QA进行深色浅色切换说输入框光标颜色没有改变&#xff0c;转UI结果UI说需要修改&#xff01;&#xff01;&#xff01;&#xff01;&#xff01; 本来有方法可以设置&#xff0c;但是 设置后未生效。重新进入该页面才生效&#xff01;&a…...

202488读书笔记|《365日创意文案》——无聊的 到底是这世间, 还是自己?懂得忘却的人才能前进

202488读书笔记|《365日创意文案》——无聊的 到底是这世间&#xff0c; 还是自己&#xff1f;懂得忘却的人才能前进 1月2月3月4月5月6月7月8月9月10月11月12月 《365日创意文案》WRITES PUBLISHING&#xff0c;一些日常&#xff0c;是烟火&#xff0c;也是幸福的印记。 当下也…...

linux 错误码总结

1,错误码的概念与作用 在Linux系统中,错误码是系统调用或库函数在执行失败时返回的特定数值,用于指示具体的错误类型。这些错误码通过全局变量errno来存储和传递,errno由操作系统维护,保存最近一次发生的错误信息。值得注意的是,errno的值在每次系统调用或函数调用失败时…...

页面渲染流程与性能优化

页面渲染流程与性能优化详解&#xff08;完整版&#xff09; 一、现代浏览器渲染流程&#xff08;详细说明&#xff09; 1. 构建DOM树 浏览器接收到HTML文档后&#xff0c;会逐步解析并构建DOM&#xff08;Document Object Model&#xff09;树。具体过程如下&#xff1a; (…...

HarmonyOS运动开发:如何用mpchart绘制运动配速图表

##鸿蒙核心技术##运动开发##Sensor Service Kit&#xff08;传感器服务&#xff09;# 前言 在运动类应用中&#xff0c;运动数据的可视化是提升用户体验的重要环节。通过直观的图表展示运动过程中的关键数据&#xff0c;如配速、距离、卡路里消耗等&#xff0c;用户可以更清晰…...

JS设计模式(4):观察者模式

JS设计模式(4):观察者模式 一、引入 在开发中&#xff0c;我们经常会遇到这样的场景&#xff1a;一个对象的状态变化需要自动通知其他对象&#xff0c;比如&#xff1a; 电商平台中&#xff0c;商品库存变化时需要通知所有订阅该商品的用户&#xff1b;新闻网站中&#xff0…...

k8s从入门到放弃之HPA控制器

k8s从入门到放弃之HPA控制器 Kubernetes中的Horizontal Pod Autoscaler (HPA)控制器是一种用于自动扩展部署、副本集或复制控制器中Pod数量的机制。它可以根据观察到的CPU利用率&#xff08;或其他自定义指标&#xff09;来调整这些对象的规模&#xff0c;从而帮助应用程序在负…...

解决MybatisPlus使用Druid1.2.11连接池查询PG数据库报Merge sql error的一种办法

目录 前言 一、问题重现 1、环境说明 2、重现步骤 3、错误信息 二、关于LATERAL 1、Lateral作用场景 2、在四至场景中使用 三、问题解决之道 1、源码追踪 2、关闭sql合并 3、改写处理SQL 四、总结 前言 在博客&#xff1a;【写在创作纪念日】基于SpringBoot和PostG…...

信息系统分析与设计复习

2024试卷 单选题&#xff08;20&#xff09; 1、在一个聊天系统(类似ChatGPT)中&#xff0c;属于控制类的是&#xff08;&#xff09;。 A. 话语者类 B.聊天文字输入界面类 C. 聊天主题辨别类 D. 聊天历史类 ​解析 B-C-E备选架构中分析类分为边界类、控制类和实体类。 边界…...

NoSQL——Redis配置与优化

目录 关系型&非关系型数据库 一、核心原理对比‌ ‌二、核心特性对比‌ ‌三、关键区别剖析‌ ‌四、典型产品示例‌ ‌总结‌ Redis Redis核心原理 核心特性 技术意义 配置文件解析 1. 基础配置 2. 持久化配置 3. 内存管理 4. 高可用配置 5. 性能调优 6.…...

循环神经网络(RNN):从理论到翻译

循环神经网络&#xff08;RNN&#xff09;是一种专为处理序列数据设计的神经网络&#xff0c;如时间序列、自然语言或语音。与传统的全连接神经网络不同&#xff0c;RNN具有"记忆"功能&#xff0c;通过循环传递信息&#xff0c;使其特别适合需要考虑上下文或顺序的任…...

低代码采购系统搭建:鲸采云+能源行业订单管理自动化案例

在能源行业数字化转型浪潮下&#xff0c;某大型能源集团通过鲸采云低代码平台&#xff0c;仅用3周时间就完成了采购订单管理系统的定制化搭建。本文将揭秘这一成功案例的实施路径与关键成效。 项目背景与挑战 该企业面临&#xff1a; 供应商分散&#xff1a;200供应商使用不同…...