哪里有免费的网站模板下载,中国建筑网查询,wordpress 搭建个人博客,网页制作 视频教程108.冗余连接#xff1a;
文章链接 题目链接#xff1a;108.冗余连接
思路
首先分析题目#xff0c;给定拥有n个节点和n条边的图#xff0c;其中图是在原n个节点和n - 1条无环无向图中添加一条边得到的。要求是输出多出的边。#xff08;PS#xff1a;可能会有多个答案…108.冗余连接
文章链接 题目链接108.冗余连接
思路
首先分析题目给定拥有n个节点和n条边的图其中图是在原n个节点和n - 1条无环无向图中添加一条边得到的。要求是输出多出的边。PS可能会有多个答案 比如下图121323都是可能的答案 还是分析题目题目可知是得到多出来的可以删除的边而结合题目给的条件可知多出来的边即添加时对应的节点已经在同一个集合中也就是成环。 也就是用并查集添加边当添加的边的节点已经在集合中时该边就是需要删除的边。 下面采用的是join函数增加一个返回值的情况
也可以是join没有返回值先is_same判断是否在一个集合中再加入集合class UnionFind():def __init__(self, size):self.parent [x for x in range(size 1)] # 节点编号从1开始def find(self, u):if self.parent[u] ! u:self.parent[u] self.find(self.parent[u])return self.parent[u]def is_same(self, u, v):return self.parent[u] self.parent[v]def join(self, u, v): # 添加v→uroot_v self.find(v)root_u self.find(u)if root_u ! root_v: # 原本不存在这条路径self.parent[root_v] root_ureturn 1return 0 # 原本存在这条路径def main():n int(input())uf UnionFind(n 1)for _ in range(n):s, t map(int, input().split())if uf.join(s,t) 0: # 原本存在这条路径print(str(s) str(t))returnif __name__ __main__:main() 109.冗余连接Ⅱ
本题比上题难得多删除边一共有三种情况 存在入度为2的节点随便删除该节点上一条边但是题目要求是多条边可以删除的话删除后出现的边 存在入度为2的节点只能删除特地一条边如下图只能删除23这条边 不存在入度为2的节点存在环那么删除使之成环的边即可 那么处理方式为需要保存边 首先统计节点的入度然后逆序保存该节点对应的两条边的序号在vec如果存在入度为2的节点对应情况1和情况2 而情况1和2的区别在于逆序删除边后剩下的节点和边组成的是否还是组成树而不是环那么就用到了并查集使用并查集判断删除vec[0]后的节点是否成环不成环为情况1可以删除当前序号对应的边否则为情况2删除vec[1]对应的边 不存在入度为2的节点存在环直接使用并查集查找使之成环的边并删除即打印。 PS使用并查集查找是否成环用的是上一题 学习收获
冗余连接无向图直接用并查集找到使之成环的边即可 冗余连接Ⅱ三种情况需要统计入度区分删除一个节点后是否成环以及原节点和边组成的有向图是否成环
