代码随想录算法训练营第六十二天 | 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,一些日常,是烟火,也是幸福的印记。 当下也…...

【大模型RAG】拍照搜题技术架构速览:三层管道、两级检索、兜底大模型
摘要 拍照搜题系统采用“三层管道(多模态 OCR → 语义检索 → 答案渲染)、两级检索(倒排 BM25 向量 HNSW)并以大语言模型兜底”的整体框架: 多模态 OCR 层 将题目图片经过超分、去噪、倾斜校正后,分别用…...
OpenLayers 可视化之热力图
注:当前使用的是 ol 5.3.0 版本,天地图使用的key请到天地图官网申请,并替换为自己的key 热力图(Heatmap)又叫热点图,是一种通过特殊高亮显示事物密度分布、变化趋势的数据可视化技术。采用颜色的深浅来显示…...

Linux 文件类型,目录与路径,文件与目录管理
文件类型 后面的字符表示文件类型标志 普通文件:-(纯文本文件,二进制文件,数据格式文件) 如文本文件、图片、程序文件等。 目录文件:d(directory) 用来存放其他文件或子目录。 设备…...

大话软工笔记—需求分析概述
需求分析,就是要对需求调研收集到的资料信息逐个地进行拆分、研究,从大量的不确定“需求”中确定出哪些需求最终要转换为确定的“功能需求”。 需求分析的作用非常重要,后续设计的依据主要来自于需求分析的成果,包括: 项目的目的…...

iPhone密码忘记了办?iPhoneUnlocker,iPhone解锁工具Aiseesoft iPhone Unlocker 高级注册版分享
平时用 iPhone 的时候,难免会碰到解锁的麻烦事。比如密码忘了、人脸识别 / 指纹识别突然不灵,或者买了二手 iPhone 却被原来的 iCloud 账号锁住,这时候就需要靠谱的解锁工具来帮忙了。Aiseesoft iPhone Unlocker 就是专门解决这些问题的软件&…...

DIY|Mac 搭建 ESP-IDF 开发环境及编译小智 AI
前一阵子在百度 AI 开发者大会上,看到基于小智 AI DIY 玩具的演示,感觉有点意思,想着自己也来试试。 如果只是想烧录现成的固件,乐鑫官方除了提供了 Windows 版本的 Flash 下载工具 之外,还提供了基于网页版的 ESP LA…...
【HarmonyOS 5 开发速记】如何获取用户信息(头像/昵称/手机号)
1.获取 authorizationCode: 2.利用 authorizationCode 获取 accessToken:文档中心 3.获取手机:文档中心 4.获取昵称头像:文档中心 首先创建 request 若要获取手机号,scope必填 phone,permissions 必填 …...

安宝特方案丨船舶智造的“AR+AI+作业标准化管理解决方案”(装配)
船舶制造装配管理现状:装配工作依赖人工经验,装配工人凭借长期实践积累的操作技巧完成零部件组装。企业通常制定了装配作业指导书,但在实际执行中,工人对指导书的理解和遵循程度参差不齐。 船舶装配过程中的挑战与需求 挑战 (1…...
在Ubuntu24上采用Wine打开SourceInsight
1. 安装wine sudo apt install wine 2. 安装32位库支持,SourceInsight是32位程序 sudo dpkg --add-architecture i386 sudo apt update sudo apt install wine32:i386 3. 验证安装 wine --version 4. 安装必要的字体和库(解决显示问题) sudo apt install fonts-wqy…...
Go 语言并发编程基础:无缓冲与有缓冲通道
在上一章节中,我们了解了 Channel 的基本用法。本章将重点分析 Go 中通道的两种类型 —— 无缓冲通道与有缓冲通道,它们在并发编程中各具特点和应用场景。 一、通道的基本分类 类型定义形式特点无缓冲通道make(chan T)发送和接收都必须准备好࿰…...