代码随想录算法训练营第六十二天 | 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. 冗余连接 题目链接:https://kamacoder.com/problempage.php?pid1181 文档讲解:https://www.programmercarl.com/kamacoder/0108.%E5%86%97%E4%BD%99%E8%BF… 思路 从前向后遍历每一条边(因为优先让前面的边连上)࿰…...

昇思MindSpore学习笔记6-01LLM原理和实践--FCN图像语义分割
摘要: 记录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日晚间,美股开盘后,美国生物制药公司Morphic股价一度暴升超75%。音讯面上,生物医药巨子礼来公司官宣,将以57美元/股的价格现金收买Morphic,较上星期五的收盘价溢价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 编程语言入门案例教程,内容包括 Mojo 的基本概念、变量、控制结构、函数等方面: Mojo 的基本概念 1.什么是 Mojo?:Mojo 是一种函数式编程语言,用于开发小型应用程序、脚本和工具。 2.Mojo 的特点&#x…...
如何在window执行mkfile
1、Windows cmd中出现错误:“‘make‘ 不是内部或外部命令,也不是可运行的程序或批处理文件。”的解决方法_windows_是板栗啊-GitCode 开源社区 2、安装cmder,再通过包管理工具下载make...
Nginx 是一个非常流行的 Web 服务器和反向代理服务器
Nginx 是一个非常流行的 Web 服务器和反向代理服务器,以其高性能、稳定性、丰富的功能集和低资源消耗而闻名。下面是一个简化的 Nginx 使用教程,包括基本的安装、配置和一些常见用途。 安装 Nginx 在 Ubuntu/Debian 上安装: sudo apt upda…...
mysql怎么调整缓冲区大小
MySQL中调整缓冲区大小是数据库性能优化的重要一环。缓冲区大小直接影响了数据库的读写性能和响应速度。以下是一些常见的MySQL缓冲区及其调整方法: 一、InnoDB缓冲池(InnoDB Buffer Pool) InnoDB缓冲池是InnoDB存储引擎用来缓存表数据和索…...

计算机组成原理学习笔记(一)
计算机组成原理 [类型:: [[计算机基础课程]] ] [来源:: [[B站]] ] [主讲人:: [[咸鱼学长]] ] [评价:: ] [知识点:: [[系统软件]] & [[应用软件]] ] [简单解释:: 管理计算机系统的软件; 按照任务需要编写的程序 ] [问题:: ] [知识点:: [[机器字长]] ] [简单…...
Vue3 对跳转 同一路由传入不同参数的页面分别进行缓存
1:使用场景 从列表页跳转至不同的详情页面,对这些详情页面分别进行缓存 2:核心代码 2.1: 配置路由文件 在路由文件里对需要进行缓存的路由对象添加meta 属性 // 需要缓存的详情页面路由 { name: detail, path: /myRouter/detail…...
LinearLayout的测量流程
在日常开发中我们常常使用LinearLayout作为布局Group,本文从其源码实现出发分析测量流程。大家可以带着问题进入下面的分析流程,看看是否能找到答案。 垂直测量 View的测量入口方法是onmeasure方法。LinearLayout的onMeasure方法根据其方向而做不同的处…...
数据无忧:Ubuntu 系统迁移备份全指南
唠唠闲话 最近电脑出现了一些故障,送修期间,不得不在实验室的台式机上重装系统,配环境的过程花费了不少时间。为避免未来处理类似事情时耗费时间,特此整理一些备份策略。 先做以下准备: U盘启动盘,参考 …...

中国IDC圈探访北京•光子1号金融算力中心
今天,“AI”、“大模型”是最炙手可热的话题,全球有海量人群在工作生活中使用大模型,大模型产品涉及多模态,应用范围已涵盖电商、传媒、金融、短视频、制造等众多行业。 而回看2003年的互联网记忆, “上网”“在线”是…...

[Unity入门01] Unity基本操作
参考的傅老师的教程学了一下Unity的基础操作: [傅老師/Unity教學] Unity3D基礎入門 [華梵大學] 遊戲引擎應用基礎(Unity版本) Class#01 移动:鼠标中键旋转:鼠标右键放大:鼠标滚轮飞行模式:右键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,以确保 DE…...

C++语言相关的常见面试题目(三)
1. List底层实现原理 省流: list底层实现了一个双向循环链表。 每个元素(或节点)包含三个部分:数据域(_M_Storage)、前驱指针(_M_prev)、后继指针(_M_next)。 数据域:存储实际数据。 前驱指针:指向链表中…...

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

Android 如何通过代码实时设置EditTextView光标
背景:换肤框架下,QA进行深色浅色切换说输入框光标颜色没有改变,转UI结果UI说需要修改!!!!! 本来有方法可以设置,但是 设置后未生效。重新进入该页面才生效!&a…...

202488读书笔记|《365日创意文案》——无聊的 到底是这世间, 还是自己?懂得忘却的人才能前进
202488读书笔记|《365日创意文案》——无聊的 到底是这世间, 还是自己?懂得忘却的人才能前进 1月2月3月4月5月6月7月8月9月10月11月12月 《365日创意文案》WRITES PUBLISHING,一些日常,是烟火,也是幸福的印记。 当下也…...
linux 错误码总结
1,错误码的概念与作用 在Linux系统中,错误码是系统调用或库函数在执行失败时返回的特定数值,用于指示具体的错误类型。这些错误码通过全局变量errno来存储和传递,errno由操作系统维护,保存最近一次发生的错误信息。值得注意的是,errno的值在每次系统调用或函数调用失败时…...

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

HarmonyOS运动开发:如何用mpchart绘制运动配速图表
##鸿蒙核心技术##运动开发##Sensor Service Kit(传感器服务)# 前言 在运动类应用中,运动数据的可视化是提升用户体验的重要环节。通过直观的图表展示运动过程中的关键数据,如配速、距离、卡路里消耗等,用户可以更清晰…...
JS设计模式(4):观察者模式
JS设计模式(4):观察者模式 一、引入 在开发中,我们经常会遇到这样的场景:一个对象的状态变化需要自动通知其他对象,比如: 电商平台中,商品库存变化时需要通知所有订阅该商品的用户;新闻网站中࿰…...
k8s从入门到放弃之HPA控制器
k8s从入门到放弃之HPA控制器 Kubernetes中的Horizontal Pod Autoscaler (HPA)控制器是一种用于自动扩展部署、副本集或复制控制器中Pod数量的机制。它可以根据观察到的CPU利用率(或其他自定义指标)来调整这些对象的规模,从而帮助应用程序在负…...

解决MybatisPlus使用Druid1.2.11连接池查询PG数据库报Merge sql error的一种办法
目录 前言 一、问题重现 1、环境说明 2、重现步骤 3、错误信息 二、关于LATERAL 1、Lateral作用场景 2、在四至场景中使用 三、问题解决之道 1、源码追踪 2、关闭sql合并 3、改写处理SQL 四、总结 前言 在博客:【写在创作纪念日】基于SpringBoot和PostG…...
信息系统分析与设计复习
2024试卷 单选题(20) 1、在一个聊天系统(类似ChatGPT)中,属于控制类的是()。 A. 话语者类 B.聊天文字输入界面类 C. 聊天主题辨别类 D. 聊天历史类 解析 B-C-E备选架构中分析类分为边界类、控制类和实体类。 边界…...

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

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

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