当前位置: 首页 > news >正文

LeetCode:261. 以图判树 - Python

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个条件:

  1. 这个图不存在环
  2. 这个图所有节点是连通
  3. 这个图的边数一定为 n-1, 因为如果一棵树有n个节点,那么它的边一定是n-1
  4. 是不是可以得出这样的结论:如果有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…...

杭州高职画室哪家好?如何选择高职画室?高职美术学习选哪家画室?

随着越来越多的画室开始涉足高职美术培训,根据杭州高职画室的美术学生及其家长所知,由于普通高中和高职联考之间存在巨大差异,因此许多普通高中的画室的高职班并未取得太大的成功。因此,小编为正在寻找画室的你提供介绍&#xff1…...

原型模式简介

概念: 原型模式 (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&#xff09…...

深圳企业制作宣传片群体定位的重要性

相信众多企业都拍了自己公司的宣传片,尤其是在互联网高度发达的今天,宣传片可以说成为了我们企业对外宣传最主要的方式。看着企业多样式的宣传片种类,我们该如何评价一部宣传片的好坏呢?要知道宣传片的好坏是一个相对主观的问题&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…...

检索与毒害 —— 对抗人工智能供应链攻击

作者&#xff1a;DAVE ERICKSON 在这篇文章中&#xff0c;了解人工智能大语言模型的供应链漏洞&#xff0c;以及如何利用搜索引擎的人工智能检索技术来对抗人工智能的错误信息和故意篡改。 虽然对于人工智能研究人员来说可能是新鲜事&#xff0c;但供应链攻击对于网络安全世界…...

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输出的原始数据&#xff0c;常见的有8位、10位、12位之分&#xff0c;分别表示一个像素点所占的字节数为8bit、10bit、12bit。 raw数据常见的有四种Bayer模式&#xff1a;GRBG、RGGB、BGGR&#xff08;下图…...

极简极速-Bitset (bitmap)实现考勤打卡场景

文章目录 1. redis命令行操作bitmap2. RedisTemplate操作bitmap3. Java中的Bitset 1. redis命令行操作bitmap 2. RedisTemplate操作bitmap bitmap的常见业务场景主要有日活统计&#xff08;类似的月考勤&#xff09;、点赞、BloomFilter等&#xff0c;以用户mj考勤统计为例&am…...

word如何插入图片?3种常用的方法

word作为一款常用的办公软件&#xff0c;不仅可以处理文本内容&#xff0c;还能够轻松地插入图片以丰富文档内容。插入图片可以使文档更具吸引力、可读性和信息传达能力。本文将为您介绍word如何插入图片的3种方法&#xff0c;帮助您在文档中灵活、高效地添加图像元素。 word插…...

Python/C API - 模組,型別,Tuple,例外和引用計數

Python/C API - 模組&#xff0c;型別&#xff0c;Tuple&#xff0c;例外和引用計數 前言Python/C API - Common Object StructuresPyObjectPyMethodDefPyGetSetDef Python/C API - Module ObjectsPyModuleDefPyModule_CreatePyModule_AddObjectPyModule_AddObjectRef Initiali…...

人工智能轨道交通行业周刊-第59期(2023.9.4-9.10)

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

中南大学无人机智能体的全面评估!BEDI:用于评估无人机上具身智能体的综合性基准测试

作者&#xff1a;Mingning Guo, Mengwei Wu, Jiarun He, Shaoxian Li, Haifeng Li, Chao Tao单位&#xff1a;中南大学地球科学与信息物理学院论文标题&#xff1a;BEDI: A Comprehensive Benchmark for Evaluating Embodied Agents on UAVs论文链接&#xff1a;https://arxiv.…...

《Playwright:微软的自动化测试工具详解》

Playwright 简介:声明内容来自网络&#xff0c;将内容拼接整理出来的文档 Playwright 是微软开发的自动化测试工具&#xff0c;支持 Chrome、Firefox、Safari 等主流浏览器&#xff0c;提供多语言 API&#xff08;Python、JavaScript、Java、.NET&#xff09;。它的特点包括&a…...

将对透视变换后的图像使用Otsu进行阈值化,来分离黑色和白色像素。这句话中的Otsu是什么意思?

Otsu 是一种自动阈值化方法&#xff0c;用于将图像分割为前景和背景。它通过最小化图像的类内方差或等价地最大化类间方差来选择最佳阈值。这种方法特别适用于图像的二值化处理&#xff0c;能够自动确定一个阈值&#xff0c;将图像中的像素分为黑色和白色两类。 Otsu 方法的原…...

使用van-uploader 的UI组件,结合vue2如何实现图片上传组件的封装

以下是基于 vant-ui&#xff08;适配 Vue2 版本 &#xff09;实现截图中照片上传预览、删除功能&#xff0c;并封装成可复用组件的完整代码&#xff0c;包含样式和逻辑实现&#xff0c;可直接在 Vue2 项目中使用&#xff1a; 1. 封装的图片上传组件 ImageUploader.vue <te…...

学习STC51单片机31(芯片为STC89C52RCRC)OLED显示屏1

每日一言 生活的美好&#xff0c;总是藏在那些你咬牙坚持的日子里。 硬件&#xff1a;OLED 以后要用到OLED的时候找到这个文件 OLED的设备地址 SSD1306"SSD" 是品牌缩写&#xff0c;"1306" 是产品编号。 驱动 OLED 屏幕的 IIC 总线数据传输格式 示意图 …...

算法岗面试经验分享-大模型篇

文章目录 A 基础语言模型A.1 TransformerA.2 Bert B 大语言模型结构B.1 GPTB.2 LLamaB.3 ChatGLMB.4 Qwen C 大语言模型微调C.1 Fine-tuningC.2 Adapter-tuningC.3 Prefix-tuningC.4 P-tuningC.5 LoRA A 基础语言模型 A.1 Transformer &#xff08;1&#xff09;资源 论文&a…...

MySQL 部分重点知识篇

一、数据库对象 1. 主键 定义 &#xff1a;主键是用于唯一标识表中每一行记录的字段或字段组合。它具有唯一性和非空性特点。 作用 &#xff1a;确保数据的完整性&#xff0c;便于数据的查询和管理。 示例 &#xff1a;在学生信息表中&#xff0c;学号可以作为主键&#xff…...

安卓基础(Java 和 Gradle 版本)

1. 设置项目的 JDK 版本 方法1&#xff1a;通过 Project Structure File → Project Structure... (或按 CtrlAltShiftS) 左侧选择 SDK Location 在 Gradle Settings 部分&#xff0c;设置 Gradle JDK 方法2&#xff1a;通过 Settings File → Settings... (或 CtrlAltS)…...

AD学习(3)

1 PCB封装元素组成及简单的PCB封装创建 封装的组成部分&#xff1a; &#xff08;1&#xff09;PCB焊盘&#xff1a;表层的铜 &#xff0c;top层的铜 &#xff08;2&#xff09;管脚序号&#xff1a;用来关联原理图中的管脚的序号&#xff0c;原理图的序号需要和PCB封装一一…...

2.3 物理层设备

在这个视频中&#xff0c;我们要学习工作在物理层的两种网络设备&#xff0c;分别是中继器和集线器。首先来看中继器。在计算机网络中两个节点之间&#xff0c;需要通过物理传输媒体或者说物理传输介质进行连接。像同轴电缆、双绞线就是典型的传输介质&#xff0c;假设A节点要给…...