LeetCode:261. 以图判树 - Python
问题描述:
给定从 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.以图判树。只在本地验证了,没有在线验证。
声明: 总结学习,有问题或不当之处,可以批评指正哦,谢谢。
相关文章:
LeetCode:261. 以图判树 - Python
261. 以图判树 问题描述: 给定从 0 到 n-1 标号的 n 个结点,和一个无向边列表(每条边以结点对来表示),请编写一个函数用来判断这些边是否能够形成一个合法有效的树结构。 示例 1: 输入:n 5, …...

Linux目录结构和远程使用
目录名作用根目录 ‘/’文件系统结构的起始点/root系统管理员的工作目录/home普通用户工作目录/bin存放二进制可执行文件,存放最经常使用的命令/sbin系统管理员使用的系统管理程序/boot启动linux时使用的一些核心文件/dev设备文件,包括块设备和字符设备/…...

淘宝销量展示方式变更背后的逻辑
淘宝销量展示方式发生了调整,平台于8月16日将商品详情销量展示表达由【月销**件】全部换成展示【已售**件】,将30天销量改成了近365天销量。 【已售**件】统计口径:统计近365天支付的商品件数,数据更新请关注24-48小时。其中涉及销…...

Bytebase 和 GitLab 签署 Technology Partner 技术合作伙伴协议
Bytebase 和 GitLab 签署技术合作伙伴协议,携手为开发者提供流畅的数据库协作开发和管理体验。 GitLab 是世界领先的开源 AI 驱动 DevSecOps 平台,旨在帮助开发者团队更好协作、更高效交付软件。Bytebase 是一款为 DevOps 团队准备的数据库 CI/CD 工具&a…...

杭州高职画室哪家好?如何选择高职画室?高职美术学习选哪家画室?
随着越来越多的画室开始涉足高职美术培训,根据杭州高职画室的美术学生及其家长所知,由于普通高中和高职联考之间存在巨大差异,因此许多普通高中的画室的高职班并未取得太大的成功。因此,小编为正在寻找画室的你提供介绍࿱…...
原型模式简介
概念: 原型模式 (Prototype Pattern)是一种创建型设计模式,它允许通过复制现有对象来创建新对象,而无需依赖于昂贵的实例化过程。该模式基于原型实例生成新的对象,并且可以根据需要进行修改和定制。 特点: 通过克隆…...

SpringMVC(一)
1.SpringMVC简介 1.1 什么是MVC MVC是一种软件架构的思想,将软件按照模型、视图、控制器来划分 M:Model,模型层,指工程中的JavaBean,作用是处理数据 JavaBean分为两类: 一类称为实体类Bean:专门存储业务逻辑的,如Student、Us…...

树的基本概念和存储结构
一、树的基本概念 1、树的定义 树是n(n>0)个结点的有限集。当n 0时,称为空树。在任意一棵非空树中应满足: 1、有且仅有一个特定的称为根的结点。 2、当n>1时,其余节点可分为m(m>0)…...

深圳企业制作宣传片群体定位的重要性
相信众多企业都拍了自己公司的宣传片,尤其是在互联网高度发达的今天,宣传片可以说成为了我们企业对外宣传最主要的方式。看着企业多样式的宣传片种类,我们该如何评价一部宣传片的好坏呢?要知道宣传片的好坏是一个相对主观的问题&a…...
2309亚当arsd的11.1版本
原文 arsd11.1 Minigui 调整主题 在11.0中略有修改Minigui的主题,但它落后于11.1的计划.这是个重大更改,但这些更改很小. 新主题稍微变浅了默认组件的背景色和默认字体,这两者都主要影响Linux,因为窗口上的大多数组件一般使用本地主题. 更改状态栏 现有的状态栏类允许添加…...

spring---第七篇
系列文章目录 文章目录 系列文章目录一、什么是bean的自动装配,有哪些方式?一、什么是bean的自动装配,有哪些方式? 开启自动装配,只需要在xml配置文件中定义“autowire”属性。 <bean id="cutomer" class="com.xxx.xxx.Customer" autowire="…...
编程要搞明白的东西(二)
文章目录 一、简介二、面向对象编程基础2.1 面向对象编程概述2.2 类和对象2.2.1 类的定义和特点2.2.2 对象的创建和使用 2.3 封装、继承与多态的关系2.3.1 封装的概念和优势2.3.2 继承的概念和作用2.3.3 多态的概念和实现方式 三、封装3.1 封装的定义和原则3.2 封装的实现方法3…...

检索与毒害 —— 对抗人工智能供应链攻击
作者:DAVE ERICKSON 在这篇文章中,了解人工智能大语言模型的供应链漏洞,以及如何利用搜索引擎的人工智能检索技术来对抗人工智能的错误信息和故意篡改。 虽然对于人工智能研究人员来说可能是新鲜事,但供应链攻击对于网络安全世界…...
Linux 禁止用户或 IP通过 SSH 登录
Linux 禁止用户或 IP通过 SSH 登录 限制用户 SSH 登录 1.只允许指定用户进行登录(白名单): 在 /etc/ssh/sshd_config 配置文件中设置 AllowUsers 选项,(配置完成需要重启 SSHD 服务)格式如下: AllowUsers aliyun test@192.168.1.1 # 允许 aliyun 和从 19…...

14.Redis 主从复制
Redis 主从复制 redis 主从复制配置 redis 主从复制启动 redis 主从复制断开 redis 主从复制主从复制构特点主从复制的拓扑结构一主一从⼀主多从树状主从 主从复制原理数据同步psync 运行流程全量复制流程部分复制流程实时复制 关于从节点何时晋升成主节点总结 redis 主从复制 …...

常见的图像格式介绍:RAW、RGB、YUV
常见的图像格式有RAW、RGB、YUV这三大类 1. RAW raw图像指的是sensor输出的原始数据,常见的有8位、10位、12位之分,分别表示一个像素点所占的字节数为8bit、10bit、12bit。 raw数据常见的有四种Bayer模式:GRBG、RGGB、BGGR(下图…...

极简极速-Bitset (bitmap)实现考勤打卡场景
文章目录 1. redis命令行操作bitmap2. RedisTemplate操作bitmap3. Java中的Bitset 1. redis命令行操作bitmap 2. RedisTemplate操作bitmap bitmap的常见业务场景主要有日活统计(类似的月考勤)、点赞、BloomFilter等,以用户mj考勤统计为例&am…...

word如何插入图片?3种常用的方法
word作为一款常用的办公软件,不仅可以处理文本内容,还能够轻松地插入图片以丰富文档内容。插入图片可以使文档更具吸引力、可读性和信息传达能力。本文将为您介绍word如何插入图片的3种方法,帮助您在文档中灵活、高效地添加图像元素。 word插…...
Python/C API - 模組,型別,Tuple,例外和引用計數
Python/C API - 模組,型別,Tuple,例外和引用計數 前言Python/C API - Common Object StructuresPyObjectPyMethodDefPyGetSetDef Python/C API - Module ObjectsPyModuleDefPyModule_CreatePyModule_AddObjectPyModule_AddObjectRef Initiali…...

人工智能轨道交通行业周刊-第59期(2023.9.4-9.10)
本期关键词:无锡智慧地铁、无人车站、钢轨打磨、混元大模型、开源大模型 1 整理涉及公众号名单 1.1 行业类 RT轨道交通人民铁道世界轨道交通资讯网铁路信号技术交流北京铁路轨道交通网上榜铁路视点ITS World轨道交通联盟VSTR铁路与城市轨道交通RailMetro轨道世界…...

css实现圆环展示百分比,根据值动态展示所占比例
代码如下 <view class""><view class"circle-chart"><view v-if"!!num" class"pie-item" :style"{background: conic-gradient(var(--one-color) 0%,#E9E6F1 ${num}%),}"></view><view v-else …...

【JVM】- 内存结构
引言 JVM:Java Virtual Machine 定义:Java虚拟机,Java二进制字节码的运行环境好处: 一次编写,到处运行自动内存管理,垃圾回收的功能数组下标越界检查(会抛异常,不会覆盖到其他代码…...
TRS收益互换:跨境资本流动的金融创新工具与系统化解决方案
一、TRS收益互换的本质与业务逻辑 (一)概念解析 TRS(Total Return Swap)收益互换是一种金融衍生工具,指交易双方约定在未来一定期限内,基于特定资产或指数的表现进行现金流交换的协议。其核心特征包括&am…...
MySQL用户和授权
开放MySQL白名单 可以通过iptables-save命令确认对应客户端ip是否可以访问MySQL服务: test: # iptables-save | grep 3306 -A mp_srv_whitelist -s 172.16.14.102/32 -p tcp -m tcp --dport 3306 -j ACCEPT -A mp_srv_whitelist -s 172.16.4.16/32 -p tcp -m tcp -…...

AI+无人机如何守护濒危物种?YOLOv8实现95%精准识别
【导读】 野生动物监测在理解和保护生态系统中发挥着至关重要的作用。然而,传统的野生动物观察方法往往耗时耗力、成本高昂且范围有限。无人机的出现为野生动物监测提供了有前景的替代方案,能够实现大范围覆盖并远程采集数据。尽管具备这些优势…...

wpf在image控件上快速显示内存图像
wpf在image控件上快速显示内存图像https://www.cnblogs.com/haodafeng/p/10431387.html 如果你在寻找能够快速在image控件刷新大图像(比如分辨率3000*3000的图像)的办法,尤其是想把内存中的裸数据(只有图像的数据,不包…...
【SpringBoot自动化部署】
SpringBoot自动化部署方法 使用Jenkins进行持续集成与部署 Jenkins是最常用的自动化部署工具之一,能够实现代码拉取、构建、测试和部署的全流程自动化。 配置Jenkins任务时,需要添加Git仓库地址和凭证,设置构建触发器(如GitHub…...
Leetcode33( 搜索旋转排序数组)
题目表述 整数数组 nums 按升序排列,数组中的值 互不相同 。 在传递给函数之前,nums 在预先未知的某个下标 k(0 < k < nums.length)上进行了 旋转,使数组变为 [nums[k], nums[k1], …, nums[n-1], nums[0], nu…...
【Kafka】Kafka从入门到实战:构建高吞吐量分布式消息系统
Kafka从入门到实战:构建高吞吐量分布式消息系统 一、Kafka概述 Apache Kafka是一个分布式流处理平台,最初由LinkedIn开发,后成为Apache顶级项目。它被设计用于高吞吐量、低延迟的消息处理,能够处理来自多个生产者的海量数据,并将这些数据实时传递给消费者。 Kafka核心特…...
Python爬虫实战:研究Restkit库相关技术
1. 引言 1.1 研究背景与意义 在当今信息爆炸的时代,互联网上存在着海量的有价值数据。如何高效地采集这些数据并将其应用于实际业务中,成为了许多企业和开发者关注的焦点。网络爬虫技术作为一种自动化的数据采集工具,可以帮助我们从网页中提取所需的信息。而 RESTful API …...