Day50 | 108.冗余连接 109.冗余连接II

108.冗余连接

108. 冗余连接

题目

题目描述

树可以看成是一个图(拥有 n 个节点和 n - 1 条边的连通无环无向图)。 

现给定一个拥有 n 个节点(节点标号是从 1 到 n)和 n 条边的连通无向图,请找出一条可以删除的边,删除后图可以变成一棵树。

输入描述

第一行包含一个整数 N,表示图的节点个数和边的个数。

后续 N 行,每行包含两个整数 s 和 t,表示图中 s 和 t 之间有一条边。

输出描述

输出一条可以删除的边。如果有多个答案,请删除标准输入中最后出现的那条边。

思路

  1. 定义并查集结构:

    • 使用一个数组 father 来表示每个节点的父节点。初始状态下,每个节点都是自己的父节点(即每个节点都代表一个单独的集合)。
  2. 初始化并查集 (init 方法):

    • 遍历所有节点,将每个节点设置为其自身的父节点。这一步是为了建立每个节点独立的集合。
  3. 查找根节点 (find 方法):

    • 对于给定的节点 u,如果 u 不是自己的父节点,就递归地查找其父节点的根节点,直到找到根节点为止。在这个过程中,会将路径上的所有节点指向根节点以优化查询效率(路径压缩)。
  4. 判断是否在同一集合 (isSame 方法):

    • 分别查找两个节点 u 和 v 的根节点,如果它们的根节点相同,则表示这两个节点属于同一个集合。
  5. 合并两个集合 (join 方法):

    • 查找两个节点 u 和 v 的根节点。如果它们的根节点不同,则将其中一个根节点的父节点设为另一个根节点,从而实现两个集合的合并。
  6. 主函数逻辑 (main 方法):

    • 从标准输入读取节点数量 n
    • 创建一个 UnionFindExample 实例,并调用 init 方法进行初始化。
    • 读取每一对节点 s 和 t,如果它们已经在同一个集合中(通过 isSame 方法判断),则输出这对节点并结束程序;否则,将这对节点所在的集合合并(通过 join 方法)。

代码

import java.util.Scanner;
import java.util.Arrays;public class Main {private int n; // 节点数量private int[] father; // 数组用于存储每个节点的父节点// 构造函数public Main(int n) {this.n = n;this.father = new int[n + 1];Arrays.fill(father, 0);}// 初始化并查集结构public void init() {for (int i = 0; i <= n; ++i) {father[i] = i;}}// 查找给定节点的根节点public int find(int u) {return u == father[u] ? u : (father[u] = find(father[u]));}// 检查两个节点是否属于同一集合public boolean isSame(int u, int v) {u = find(u);v = find(v);return u == v;}// 将两个集合合并,通过链接第二个集合的根节点到第一个集合的根节点public void join(int u, int v) {u = find(u);v = find(v);if (u == v) return;father[v] = u;}public static void main(String[] args) {Scanner scanner = new Scanner(System.in);Main uf = new Main(scanner.nextInt());uf.init();while (scanner.hasNextInt()) {int s = scanner.nextInt();int t = scanner.nextInt();if (uf.isSame(s, t)) {System.out.println(s + " " + t);return;} else {uf.join(s, t);}}}
}

易错点

在 find 方法中,递归地查找根节点的同时,需要更新路径上的每个节点的父节点指向根节点,以减少未来的查找时间

109.冗余连接II

109. 冗余连接II

题目

题目描述

有一种有向树,该树只有一个根节点,所有其他节点都是该根节点的后继。该树除了根节点之外的每一个节点都有且只有一个父节点,而根节点没有父节点。有向树拥有 n 个节点和 n - 1 条边。如图: 

现在有一个有向图,有向图是在有向树中的两个没有直接链接的节点中间添加一条有向边。如图:

输入一个有向图,该图由一个有着 n 个节点(节点编号 从 1 到 n),n 条边,请返回一条可以删除的边,使得删除该条边之后该有向图可以被当作一颗有向树。

输入描述

第一行输入一个整数 N,表示有向图中节点和边的个数。 

后续 N 行,每行输入两个整数 s 和 t,代表这是 s 节点连接并指向 t 节点的单向边

输出描述

输出一条可以删除的边,若有多条边可以删除,请输出标准输入中最后出现的一条边。

思路

  1. 初始化并查集: 使用一个数组 father 来表示每个节点的父节点。初始状态下,每个节点都是自己的父节点。
  2. 查找根节点 (find 方法): 对于给定的节点 u,如果 u 不是自己的父节点,就递归地查找其父节点的根节点,直到找到根节点为止。在这个过程中,会将路径上的所有节点指向根节点以优化查询效率(路径压缩)。
  3. 合并两个集合 (join 方法): 查找两个节点 u 和 v 的根节点。如果它们的根节点不同,则将其中一个根节点的父节点设为另一个根节点,从而实现两个集合的合并。
  4. 检测有向环 (getRemoveEdge 方法): 遍历每条边,如果两个端点已经在同一个集合中,则输出这条边并结束程序。
  5. 检测删除边后是否为树 (isTreeAfterRemoveEdge 方法): 删除指定的边后,再次遍历所有的边,如果存在环,则返回 false,否则返回 true
  6. 主函数逻辑 (main 方法):
    • 从标准输入读取节点数量 n
    • 创建一个 Main 实例,并调用 init 方法进行初始化。
    • 读取每对节点 s 和 t,并记录每个节点的入度。
    • 根据入度的不同情况选择删除的边。
      • 如果存在入度为2的节点,优先删除最后一条指向该节点的边。
      • 如果不存在入度为2的节点但存在环,删除构成环的任意一条边。

代码

import java.util.Scanner;
import java.util.ArrayList;
import java.util.List;
import java.util.Arrays;public class Main {private int n;private int[] father;public Main(int n) {this.n = n;this.father = new int[n + 1];Arrays.fill(father, 0);}// 初始化并查集public void init() {for (int i = 1; i <= n; ++i) {father[i] = i;}}// 查找给定节点的根节点public int find(int u) {return u == father[u] ? u : (father[u] = find(father[u]));}// 将两个集合合并public void join(int u, int v) {u = find(u);v = find(v);if (u == v) return;father[v] = u;}// 检查两个节点是否属于同一集合public boolean same(int u, int v) {u = find(u);v = find(v);return u == v;}// 在有向图里找到删除的那条边,使其变成树public void getRemoveEdge(List<List<Integer>> edges) {init(); // 初始化并查集for (List<Integer> edge : edges) { // 遍历所有的边if (same(edge.get(0), edge.get(1))) { // 构成有向环了,就是要删除的边System.out.println(edge.get(0) + " " + edge.get(1));return;} else {join(edge.get(0), edge.get(1));}}}// 删一条边之后判断是不是树public boolean isTreeAfterRemoveEdge(List<List<Integer>> edges, int deleteEdge) {init(); // 初始化并查集for (int i = 0; i < edges.size(); i++) {if (i == deleteEdge) continue;List<Integer> edge = edges.get(i);if (same(edge.get(0), edge.get(1))) { // 构成有向环了,一定不是树return false;}join(edge.get(0), edge.get(1));}return true;}public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();Main uf = new Main(n);List<List<Integer>> edges = new ArrayList<>();int[] inDegree = new int[n + 1]; // 记录节点入度for (int i = 0; i < n; i++) {int s = scanner.nextInt();int t = scanner.nextInt();inDegree[t]++;edges.add(new ArrayList<>(Arrays.asList(s, t))); // 使用 ArrayList 替代 List.of}List<Integer> vec = new ArrayList<>(); // 记录入度为2的边(如果有的话就两条边)// 找入度为2的节点所对应的边,注意要倒序,因为优先删除最后出现的一条边for (int i = n - 1; i >= 0; i--) {if (inDegree[edges.get(i).get(1)] == 2) {vec.add(i);}}// 情况一、情况二if (!vec.isEmpty()) {// 放在vec里的边已经按照倒叙放的,所以这里就优先删vec.get(0)这条边if (uf.isTreeAfterRemoveEdge(edges, vec.get(0))) {List<Integer> edgeToRemove = edges.get(vec.get(0));System.out.println(edgeToRemove.get(0) + " " + edgeToRemove.get(1));} else {List<Integer> edgeToRemove = edges.get(vec.get(1));System.out.println(edgeToRemove.get(0) + " " + edgeToRemove.get(1));}return;}// 处理情况三// 明确没有入度为2的情况,那么一定有有向环,找到构成环的边返回就可以了uf.getRemoveEdge(edges);}
}

易错点

在处理入度为2的节点时,需要确保正确地识别哪些边需要被删除。

在删除边后判断是否为树的过程中,需要注意删除边后重新初始化并查集,避免使用之前的状态。

总结

继续图论知识。

明天继续加油!

勤学苦练硕果累累,虚度光阴两手空空

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/411271.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

一个简单的CRM客户信息管理系统,提供客户,线索,公海,联系人,跟进信息和数据统计功能(附源码)

前言 在当今快速发展的商业环境中&#xff0c;企业管理面临着种种挑战&#xff0c;尤其是如何有效管理和维护客户关系成为了一个关键问题。现有的一些处理方案往往存在功能分散、操作复杂、数据孤岛等痛点&#xff0c;这不仅影响了工作效率&#xff0c;也难以满足企业对客户关…

使用kafka完成数据的实时同步,同步到es中。(使用kafka实现自动上下架 upper、lower)

文章目录 1、发送消息 KafkaService2、生产者 service-album -> AlbumInfoServiceImpl2.1、新增 saveAlbumInfo()2.2、更新 updateAlbumInfo()2.3、删除 removeAlbumInfo() 3、消费者 service-search - > AlbumListener.java 上架&#xff1a;新增专辑到 es下架&#xff…

【归纳总结】常见排序算法及其实现:直接插入排序、希尔排序、选择排序、堆排序、冒泡排序、快排、归并排序

思维导图&#xff1a; 目录 思维导图&#xff1a; 一、插入排序 1.直接插入排序&#xff1a; a:基本思想&#xff1a; b:基本步骤&#xff1a; c:复杂度分析 d:Java代码实现&#xff1a; 2.希尔排序&#xff08;缩小增量排序&#xff09; a:基本思想&#xff1a; c…

用AI来学习英语口语(白嫖,所以稍微麻烦些)

写在前面 本文看下如何使用AI来免费学习英语口语。 1&#xff1a;正文 首先&#xff0c;我们点击这里来到一个对话窗口&#xff0c;你可以在这个窗口中使用英语来询问你的问题&#xff0c;比如what can i do when i am not happy&#xff1a; 接着复制机器人回答内容&#…

离散数学中的逻辑基础(1)

目录 引言 1. 命题及其逻辑运算 2. 逻辑等价与范式 3. 逻辑推理规则 4. 逻辑问题练习 5. 总结 引言 逻辑是离散数学的核心概念之一&#xff0c;它用于精确描述数学命题并分析其关系。逻辑不仅是数学证明的基础&#xff0c;也是计算机科学中算法设计和编程的基石。本篇文…

minio文件存储+ckplayer视频播放(minio分片上传合并视频播放)

文章目录 参考简述效果启动minio代码配置类RedisConfigWebConfigMinioClientAutoConfigurationOSSPropertiesapplication.yml 实体类MinioObjectResultStatusCodeOssFileOssPolicy 工具类FileTypeUtilMd5UtilMediaTypeMinioTemplate 文件分片上传与合并MinioFileControllerMini…

Avalonia与WPF开发时的差异总结

1.一个控件绑定到另外一个控件的属性 WPF: <TextBox Height"30" Width"100" x:Name"tb"></TextBox><TextBlock Text"{Binding ElementNametb,PathText}" ></TextBlock>Avalonia: <TextBox Height"3…

YarnClient发送和接收请求源码解析

YarnClient发送和接收请求流程 Yarn是通过RPC协议通信的&#xff0c;协议类型可以通过查看RpcKind类得知&#xff0c;总共有三种类型&#xff1a; RPC_BUILTIN ((short) 1), // Used for built in calls by tests RPC_WRITABLE ((short) 2), // Use WritableRp…

比特币的签名和验证(基于ECDSA)

比特币&#xff08;Bitcoin&#xff09;和以太坊&#xff08;Ethereum&#xff09;等区块链技术使用了加密算法来确保交易的安全性。私钥签名和公钥验证是这些算法的核心部分&#xff0c;主要用于证明交易的发起者拥有交易中使用的资金的控制权&#xff0c;而不需要暴露私钥本身…

浪潮服务器NVME 硬盘通过 Intel VROC 做RAID

INTEL VROC Configuration solution 1.VMD configuration in BIOS Processor > IIO Configuration> Intel(R) VDM Technology> Intel(R) VMD for volume Management Device on Socket 0 “CPU 0”, Intel VMD for volume management device for “PStack0” or “PSta…

【香橙派系列教程】(十七) 视觉垃圾桶-功能完善优化

【十七】视觉垃圾桶-功能完善优化 文章目录 【十七】视觉垃圾桶-功能完善优化一、增加垃圾桶开关盖1.引脚2.PWM 频率的公式3.PWM_APIsoftPwmCreatesoftPwmWrite附加说明softPwmStop 4.代码pwm.cpwm.hmain.c 二、项目代码优化编译运行 三、增加OLED 屏幕显示功能myoled.hmyoled.…

小白之 FastGPT Windows 本地化部署

目录 引言环境步骤1. 安装 docker2. 启动 docker3. 浏览器访问4. One API 配置语言模型、向量模型渠道和令牌5. 创建 FastGPT 知识库6. 创建 FastGPT 应用 官方文档 引言 部署之前可以先看一下 RAG 技术原理&#xff0c;也可以后面回过头来看&#xff0c;对一些概念有些了解&a…

Qt+FFmpeg开发视频播放器笔记(一):环境搭建

一、FFmpeg介绍 FFmpeg是一个开源的跨平台多媒体处理工具集&#xff0c;它可以用于处理音频、视频和其他多媒体数据。FFmpeg提供了一组功能强大的命令行工具&#xff0c;用于音频和视频的编解码、转换、处理、流媒体传输等任务。 FFmpeg支持多种音频和视频格式&#xff0c;包…

【自动化】考试答题自动化完成答案,如何实现100%正确呢

一、科目仿真考试不能自动答题 我的答案是可以的&#xff0c;电脑程序可以模拟人的操作完成所有的答题并提交结束考试 二、分析页面内容 完成一个题目&#xff0c;包括判断题&#xff0c;对与错2选1答案&#xff0c;单选题ABCD4选1答案&#xff0c;多选题大家想一想 F12查看按…

C语言 ——— 将动态版本的通讯录实现为文件存储联系人模式

目录 前言 在退出通讯录之前 在运行通讯录之前 前言 在这篇博客中&#xff0c;实现了动态版本的通讯录&#xff0c;接下来会增加函数&#xff0c;能用文件存储通讯录中的联系人 C语言 ——— 在控制台实现通讯录&#xff08;增删查改、动态开辟内存空间&#xff09;-CSDN…

#网络高级 笔记

modbus_tcp协议 modbus_rtu协议和modbus库 http协议和web服务器搭建 服务器原码分析和基于WebServer的工业数据采集项目 第H5&#xff0c;即网页制作&#xff0c;项目完善 一、modbus起源 1.起源 Modbus由Modicon公司于1979年开发&#xff0c;是一种工业现场总线协议标准 Mo…

python将字典数据保存为json文件

目录 一、json库介绍 二、字典生成json文件 1、导入 json 模块 2、将字典数据保存为 json 文件 (1) 创建一个python字典 (2) 指定要保存的 json 文件路径 (3) 将字典数据存为 json 文件 3、读取 json文件&#xff0c;并打印 一、json库介绍 方法作用json.dumps()将py…

对数据处理过程中,缺失值和异常值应该怎么处理?

创作不易&#xff0c;您的关注、点赞、收藏和转发是我坚持下去的动力&#xff01; 大家有技术交流指导、论文及技术文档写作指导、项目开发合作的需求可以私信联系我。 在数据处理过程中&#xff0c;缺失值和异常值的处理是非常重要的步骤&#xff0c;它们可能会对模型的性能…

Datawhale AI夏令营第五期学习!

学习日志 日期&#xff1a; 2024年8月27日 今日学习内容&#xff1a; 今天&#xff0c;我学习了如何在深度学习任务中使用卷积神经网络&#xff08;CNN&#xff09;进行图像分类的基本流程&#xff0c;并成功地在JupyterLab中运行了一个完整的项目。以下是我今天的学习和操作…

【扩散模型(六)】IP-Adapter 是如何训练的?2 源码篇(IP-Adapter Plus)

系列文章目录 【扩散模型&#xff08;二&#xff09;】IP-Adapter 从条件分支的视角&#xff0c;快速理解相关的可控生成研究【扩散模型&#xff08;三&#xff09;】IP-Adapter 源码详解1-训练输入 介绍了训练代码中的 image prompt 的输入部分&#xff0c;即 img projection…