网站网页直播怎么做的,泗洪网站建设,什么是网络营销有哪些特点,秦皇岛房产信息网261. 以图判树 问题描述#xff1a;
给定从 0 到 n-1 标号的 n 个结点#xff0c;和一个无向边列表#xff08;每条边以结点对来表示#xff09;#xff0c;请编写一个函数用来判断这些边是否能够形成一个合法有效的树结构。
示例 1#xff1a; 输入#xff1a;n 5, … 261. 以图判树 问题描述
给定从 0 到 n-1 标号的 n 个结点和一个无向边列表每条边以结点对来表示请编写一个函数用来判断这些边是否能够形成一个合法有效的树结构。
示例 1 输入n 5, 边列表 edges [[0,1], [0,2], [0,3], [1,4]] 输出true 示例 2 输入n 5, 边列表 edges [[0,1], [1,2], [2,3], [1,3], [1,4]] 输出false 注意 你可以假定边列表 edges 中不会出现重复的边。由于所有的边是无向边边 [0,1] 和边 [1,0] 是相同的因此不会同时出现在边列表 edges 中。
问题分析
这题目有点贵呀是LeetCode的VIP题目第一次见还有点蒙其实仔细想想也没啥难的。问题分析判断一个无向图能否勾成一个树很显然这个图要满足3个条件
这个图不存在环这个图所有节点是连通这个图的边数一定为 n-1 因为如果一棵树有n个节点那么它的边一定是n-1是不是可以得出这样的结论如果有n-1条边且有环是一定是不连通是不是可以说明在n-1条边的条件下只要判断是否有环即可没有环路且边数为n-1就一定能构造成树(没有严谨的证明哈感觉反证法可以证明)
现在看看题目如何做 1第一个条件就是判断这个图的边数是否等于n-1很显然不符合就直接返回 False 即可。 2使用并查集的思想判断是否存在环路如果存在环路直接返回 False否则最后就返回 True 。
Python3实现
# Time :2023/09/06
# Author :Liuclass Solution:def validTree(self, n, edges):if len(edges) ! n - 1: # 边数是否等于 n - 1return Falsedef find(x): # 并查集查找if fa[x] ! x:fa[x] find(fa[x])return fa[x]fa [i for i in range(n)]for x, y in edges: # 判断两个点是否在同一个并查集里面fa_x find(x)fa_y find(y)if fa_x fa_y:return Falsefa[fa_x] fa_yreturn Trueif __name__ __main__:solu Solution()n, edges 7, [[0, 1], [1, 2], [2, 3], [4, 5], [4, 6], [5, 6]]print(solu.validTree(n, edges))相关参考 [1]LeetCode:261. 以图判树 是VIP 题目反正我是打不开。 [2] 代码参考: yiduobo的每日leetcode 261.以图判树。只在本地验证了没有在线验证。 声明 总结学习有问题或不当之处可以批评指正哦谢谢。
