当前位置: 首页 > 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;也是幸福的印记。 当下也…...

【大模型RAG】拍照搜题技术架构速览:三层管道、两级检索、兜底大模型

摘要 拍照搜题系统采用“三层管道&#xff08;多模态 OCR → 语义检索 → 答案渲染&#xff09;、两级检索&#xff08;倒排 BM25 向量 HNSW&#xff09;并以大语言模型兜底”的整体框架&#xff1a; 多模态 OCR 层 将题目图片经过超分、去噪、倾斜校正后&#xff0c;分别用…...

OpenLayers 可视化之热力图

注&#xff1a;当前使用的是 ol 5.3.0 版本&#xff0c;天地图使用的key请到天地图官网申请&#xff0c;并替换为自己的key 热力图&#xff08;Heatmap&#xff09;又叫热点图&#xff0c;是一种通过特殊高亮显示事物密度分布、变化趋势的数据可视化技术。采用颜色的深浅来显示…...

Linux 文件类型,目录与路径,文件与目录管理

文件类型 后面的字符表示文件类型标志 普通文件&#xff1a;-&#xff08;纯文本文件&#xff0c;二进制文件&#xff0c;数据格式文件&#xff09; 如文本文件、图片、程序文件等。 目录文件&#xff1a;d&#xff08;directory&#xff09; 用来存放其他文件或子目录。 设备…...

大话软工笔记—需求分析概述

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

iPhone密码忘记了办?iPhoneUnlocker,iPhone解锁工具Aiseesoft iPhone Unlocker 高级注册版​分享

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

DIY|Mac 搭建 ESP-IDF 开发环境及编译小智 AI

前一阵子在百度 AI 开发者大会上&#xff0c;看到基于小智 AI DIY 玩具的演示&#xff0c;感觉有点意思&#xff0c;想着自己也来试试。 如果只是想烧录现成的固件&#xff0c;乐鑫官方除了提供了 Windows 版本的 Flash 下载工具 之外&#xff0c;还提供了基于网页版的 ESP LA…...

【HarmonyOS 5 开发速记】如何获取用户信息(头像/昵称/手机号)

1.获取 authorizationCode&#xff1a; 2.利用 authorizationCode 获取 accessToken&#xff1a;文档中心 3.获取手机&#xff1a;文档中心 4.获取昵称头像&#xff1a;文档中心 首先创建 request 若要获取手机号&#xff0c;scope必填 phone&#xff0c;permissions 必填 …...

安宝特方案丨船舶智造的“AR+AI+作业标准化管理解决方案”(装配)

船舶制造装配管理现状&#xff1a;装配工作依赖人工经验&#xff0c;装配工人凭借长期实践积累的操作技巧完成零部件组装。企业通常制定了装配作业指导书&#xff0c;但在实际执行中&#xff0c;工人对指导书的理解和遵循程度参差不齐。 船舶装配过程中的挑战与需求 挑战 (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 语言并发编程基础:无缓冲与有缓冲通道

在上一章节中&#xff0c;我们了解了 Channel 的基本用法。本章将重点分析 Go 中通道的两种类型 —— 无缓冲通道与有缓冲通道&#xff0c;它们在并发编程中各具特点和应用场景。 一、通道的基本分类 类型定义形式特点无缓冲通道make(chan T)发送和接收都必须准备好&#xff0…...