算法工程师第四十八天(108.冗余连接 109.冗余连接II)

2024-08-28 02:36

本文主要是介绍算法工程师第四十八天(108.冗余连接 109.冗余连接II),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

参考文献 代码随想录

一、冗余连接

题目描述

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

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

输入描述

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

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

输出描述

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

输入示例
3
1 2
2 3
1 3
输出示例
1 3
提示信息

图中的 1 2,2 3,1 3 等三条边在删除后都能使原图变为一棵合法的树。但是 1 3 由于是标准输出里最后出现的那条边,所以输出结果为 1 3

数据范围:

1 <= N <= 1000.

问题分析

这道题目也是并查集基础题目。

这里我依然降调一下,并查集可以解决什么问题:两个节点是否在一个集合,也可以将两个节点添加到一个集合中。

如果还不了解并查集,可以看这里:并查集理论基础

我们再来看一下这道题目。

题目说是无向图,返回一条可以删去的边,使得结果图是一个有着N个节点的树(即:只有一个根节点)。

如果有多个答案,则返回二维数组中最后出现的边。

那么我们就可以从前向后遍历每一条边(因为优先让前面的边连上),边的两个节点如果不在同一个集合,就加入集合(即:同一个根节点)。

如图所示:

节点A 和节点 B 不在同一个集合,那么就可以将两个 节点连在一起。

如果边的两个节点已经出现在同一个集合里,说明着边的两个节点已经连在一起了,再加入这条边一定就出现环了。

如图所示:

已经判断 节点A 和 节点B 在在同一个集合(同一个根),如果将 节点A 和 节点B 连在一起就一定会出现环。

这个思路清晰之后,代码就很好写了。

class UnionFind():def __init__(self, length):self.fa = list(range(length + 1))  # 初始化,默认自己为自己的父亲def find(self, x):if x != self.fa[x]: self.fa[x] = self.find(self.fa[x])  # 路基压缩return self.fa[x]def is_same(self, u, v):return self.find(u) == self.find(v)  # 查def join(self, u, v):fa_u = self.find(u)fa_v = self.find(v)  # 并if fa_v != fa_u:self.fa[fa_u] = fa_v# 不要形成环
n = int(input())
uf = UnionFind(n)
for i in range(n):u, v = map(int, input().split())if uf.is_same(u, v):print(u, v)else:uf.join(u, v)

二、冗余连接II

题目描述

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

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

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

输入描述

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

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

输出描述

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

输入示例
3
1 2
1 3
2 3
输出示例
2 3
提示信息

在删除 2 3 后有向图可以变为一棵合法的有向树,所以输出 2 3

数据范围:

1 <= N <= 1000.

# 有向图要构成树有两个条件
# 1。每个节点入度必须为1
# 2。不可以形成环
# 删除一条边没有形成环,删除最后一边(情况1)
# 删除一条边以后可能形成环,必须判断(情况2)
# 本身可能是环,需要删除(情况3)
class Union_search:def __init__(self, M):self.father = [i for i in range(M + 1)]def find(self, u):if u != self.father[u]:self.father[u] = self.find(self.father[u])return self.father[u]def is_same(self, u, v):f_u = self.find(u)f_v = self.find(v)return f_u == f_vdef join(self, u, v):f_u = self.find(u)f_v = self.find(v)if f_u != f_v:self.father[f_v] = f_udef find_cycle(M, sides):  # 删除环us = Union_search(M)for x, y in sides:if us.is_same(x, y):  # 如果在同一个集合里return x, yus.join(x, y)return Nonedef is_cycle_after_remove(M, del_side, sides):us = Union_search(M)  # 初始化, m是边for x, y in sides:if x == del_side[0] and y == del_side[1]:  # 如果等于我们要删除的那条边的话,就跳过continueif us.is_same(x, y):  # 如果删除del_side之后,还存在环那么,直接返回Truereturn Trueus.join(x, y)    # 不存在环return False  # 删除了之后,不存在环def main():M = int(input())sides = []  # 存放的是边in_degree = [0] * (M + 1)for i in range(M):sides.append(list(map(int, input().split())))in_degree[sides[i][1]] += 1  # 统计每个节点的入度情况# 倒叙遍历入度为2的点,并将进入这些点的边加入vecvec = []for i in range(M - 1, -1, -1):  # 倒序遍历if in_degree[sides[i][1]] == 2:   # 统计出入度为2的是哪些边vec.append(sides[i])if vec:# 正序遍历vec列表,试图删除for i in range(len(vec)):if not is_cycle_after_remove(M, vec[i], sides):  # M是节点数量, vec[i]那些边参与入度为2的节点,然后删除的是靠后的那条边print(vec[i][0], vec[i][1])returnelse:# 如果没有找到可删除的边,试图验证是否形成环?x, y = find_cycle(M, sides)print(x, y)if __name__ == "__main__":main()

这篇关于算法工程师第四十八天(108.冗余连接 109.冗余连接II)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1113479

相关文章

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.

Spring Boot 整合 MyBatis 连接数据库及常见问题

《SpringBoot整合MyBatis连接数据库及常见问题》MyBatis是一个优秀的持久层框架,支持定制化SQL、存储过程以及高级映射,下面详细介绍如何在SpringBoot项目中整合My... 目录一、基本配置1. 添加依赖2. 配置数据库连接二、项目结构三、核心组件实现(示例)1. 实体类2. Ma

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组(时间轮)和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时

电脑win32spl.dll文件丢失咋办? win32spl.dll丢失无法连接打印机修复技巧

《电脑win32spl.dll文件丢失咋办?win32spl.dll丢失无法连接打印机修复技巧》电脑突然提示win32spl.dll文件丢失,打印机死活连不上,今天就来给大家详细讲解一下这个问题的解... 不知道大家在使用电脑的时候是否遇到过关于win32spl.dll文件丢失的问题,win32spl.dl

Windows Server服务器上配置FileZilla后,FTP连接不上?

《WindowsServer服务器上配置FileZilla后,FTP连接不上?》WindowsServer服务器上配置FileZilla后,FTP连接错误和操作超时的问题,应该如何解决?首先,通过... 目录在Windohttp://www.chinasem.cnws防火墙开启的情况下,遇到的错误如下:无法与

IDEA连接达梦数据库的详细配置指南

《IDEA连接达梦数据库的详细配置指南》达梦数据库(DMDatabase)作为国产关系型数据库的代表,广泛应用于企业级系统开发,本文将详细介绍如何在IntelliJIDEA中配置并连接达梦数据库,助力... 目录准备工作1. 下载达梦JDBC驱动配置步骤1. 将驱动添加到IDEA2. 创建数据库连接连接参数

如何通过Golang的container/list实现LRU缓存算法

《如何通过Golang的container/list实现LRU缓存算法》文章介绍了Go语言中container/list包实现的双向链表,并探讨了如何使用链表实现LRU缓存,LRU缓存通过维护一个双向... 目录力扣:146. LRU 缓存主要结构 List 和 Element常用方法1. 初始化链表2.

pycharm远程连接服务器运行pytorch的过程详解

《pycharm远程连接服务器运行pytorch的过程详解》:本文主要介绍在Linux环境下使用Anaconda管理不同版本的Python环境,并通过PyCharm远程连接服务器来运行PyTorc... 目录linux部署pytorch背景介绍Anaconda安装Linux安装pytorch虚拟环境安装cu

golang字符串匹配算法解读

《golang字符串匹配算法解读》文章介绍了字符串匹配算法的原理,特别是Knuth-Morris-Pratt(KMP)算法,该算法通过构建模式串的前缀表来减少匹配时的不必要的字符比较,从而提高效率,在... 目录简介KMP实现代码总结简介字符串匹配算法主要用于在一个较长的文本串中查找一个较短的字符串(称为

通俗易懂的Java常见限流算法具体实现

《通俗易懂的Java常见限流算法具体实现》:本文主要介绍Java常见限流算法具体实现的相关资料,包括漏桶算法、令牌桶算法、Nginx限流和Redis+Lua限流的实现原理和具体步骤,并比较了它们的... 目录一、漏桶算法1.漏桶算法的思想和原理2.具体实现二、令牌桶算法1.令牌桶算法流程:2.具体实现2.1