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

可能的二分法 -- 二分图判定【DFS、BFS分别实现】

886. 可能的二分法

class PossibleBipartition:"""可能的二分法「其实考察的就是二分图的判定」用dfs和bfs 两种方法分别实现https://leetcode.cn/problems/possible-bipartition/"""def __init__(self):self.success = Trueself.color = []self.visited = []def dfs(self, n, dislikes):"""DFS递归实现:param n: :param dislikes::return:"""# 图节点编号为 1...nself.color = [False] * (n+1)self.visited = [False] * (n+1)graph = self.buildgraph(n, dislikes)# 因为图不一定是联通的,可能存在多个子图# 所以要把每个节点都作为起点进行一次遍历# 如果发现任何一个子图不是二分图,整幅图都不是二分图for v in range(1, n+1):if not self.visited[v]:self.dfs_traverse(graph, v)return self.successdef buildgraph(self, n, dislikes):graph = [[] for _ in range(n+1)]for edge in dislikes:v = edge[1]w = edge[0]# 无向图相当于双向图graph[v].append(w)graph[w].append(v)return graphdef dfs_traverse(self, graph, v):if not self.success:returnself.visited[v] = Truefor w in graph[v]:if not self.visited[w]:self.color[w] = not self.color[v]self.dfs_traverse(graph, w)else:if self.color[v] == self.color[w]:self.success = Falsereturndef bfs(self, n, dislikes):"""BFS实现,用队列替代递归调用:param n::param dislikes::return:"""# 图节点编号为 1...nself.color = [False] * (n + 1)self.visited = [False] * (n + 1)graph = self.buildgraph(n, dislikes)# 因为图不一定是联通的,可能存在多个子图# 所以要把每个节点都作为起点进行一次遍历# 如果发现任何一个子图不是二分图,整幅图都不是二分图for v in range(1, n + 1):if not self.visited[v]:self.bfs_traverse(graph, v)return self.successdef bfs_traverse(self, graph, start):# 节点队列queue = []self.visited[start] = Truequeue.append(start)while queue and self.success:v = queue.pop(0)# 从节点 v 向所有相邻节点扩散for w in graph[v]:if not self.visited[w]:# 相邻节点w没有被访问过# 那么应该给节点w涂上和节点v不同的颜⾊self.color[w] = not self.color[v]# 标记 w 节点,并放⼊队列self.visited[w] = Truequeue.append(w)else:if self.color[v] == self.color[w]:self.success = Falsereturn

相关文章:

可能的二分法 -- 二分图判定【DFS、BFS分别实现】

886. 可能的二分法 class PossibleBipartition:"""可能的二分法「其实考察的就是二分图的判定」用dfs和bfs 两种方法分别实现https://leetcode.cn/problems/possible-bipartition/"""def __init__(self):self.success Trueself.color []self.…...

六级翻译备考

classical 经典的 Chinese literature 中国文学 朝代dynasty 统治 rule 社会稳定 steady society 治理有序 orderly governance 伟大的greatest 时代 times或者periods 被人们描绘成人类历史上伴随着治理有序,社会稳定的最伟大的时代之一 more and more越来越多 …...

Vue框架--Vue中的数据绑定

Vue中有两种数据绑定的方式 1.单向数据绑定(v-band):数据只能够从data流向页面 2.双向数据绑定(v-model):数据不仅仅能够从data流向页面,也可以从页面流向data。 备注: 1.双向绑定一般都应用在表单类元素上。(如:input、select等有value属性值的标签上) 2.…...

Unity——热更新浅析

热更新的思想从本质上来讲,要考虑一些问题。例如,一个完整的游戏最多可以有多大比例的资源通过网络加载?能否让尽可能多的资源通过网络加载? 通过网络加载有很多好处,不仅可以极大减小安装包的体积,而且有…...

IMPLEMENT_DYNCREATE的分析

一、介绍 IMPLEMENT_DYNCREATE 是一个宏(macro),通常与DECLARE_DYNCREATE宏一起在MFC框架中使用。它的作用是为一个派生自 CObject 的MFC类提供运行时类型信息(RTTI)和对象的动态创建支持。 具体来说,IMP…...

Java实现根据短连接获取1688商品详情数据,1688淘口令接口,1688API接口封装方法

要通过1688的API获取商品详情数据,您可以使用1688开放平台提供的接口来实现。以下是一种使用Java编程语言实现的示例,展示如何通过1688开放平台API获取商品详情属性数据接口: 首先,确保您已注册成为1688开放平台的开发者&#xf…...

ABAP FICO 凭证替代 凭证校验

凭证校验 1.T-CODE--->GGX2--->GBLR-->ZRGGBR000 2.将程序RGGBR000 复制为ZRGGBR000 3.GGB0--》财务会计--》凭证抬头或者行项目维护检验规则 4.OB28 维护特定的公司代码和调用点和确认,活动等级设置为1 5.GGB4-->激活校验 凭证替代 1.T-CODE--->GG…...

项目验收有哪些流程?

验收流程 科技计划项目验收/课题验收测试服务的被测对象是国家重大专项、科研课题的软件成果物,可以是一个模块、软件或系统等,也可以是软件套件或软件原型等。测试范围主要来源于课题的合同书/可行吧报告/申报书中的技术指标要求。所出具的科技项目验收…...

C++,类的继承

一、继承的基本概念 继承使得C能够从已有的类派生出新的类,而派生类继承了原有类的特征,包括方法。被继承者称为父类或基类,继承者称为子类或派生类。 继承的目的: 实现代码的重用性建立父类和子类之间的联系在实现多态的时候&a…...

作业33333333

一、正向解析 在开启DNS服务之前先将防火墙关闭。 systemctl stop firewalld.service 开启DNS服务,需要开启端先进行安装主软件,以及配置包管理软件 配置包管理软件一般会跟随主软件一起安装,如果没有手动安装一次就可以了。 安装完成之后&…...

Spring Cloud--从零开始搭建微服务基础环境【二】

😀前言 本篇博文是关于Spring Cloud–从零开始搭建微服务基础环境【二】,希望你能够喜欢 🏠个人主页:晨犀主页 🧑个人简介:大家好,我是晨犀,希望我的文章可以帮助到大家,…...

算法工程题(中序遍历)

* 题意说明: * 给定一个二叉树的根节点 root ,返回 它的 中序 遍历 。 * * 示例 1: * 输入:root [1,null,2,3] * 输出:[1,3,2] * * 示例 2: * 输入:root [] * 输出:[] * *…...

jsch网页版ssh

使用依赖 implementation com.jcraft:jsch:0.1.55Server端代码 import com.jcraft.jsch.Channel; import com.jcraft.jsch.JSch; import com.jcraft.jsch.Session; import java.io.InputStream; import java.io.OutputStream; import java.util.concurrent.TimeUnit; import o…...

教程i.MX8MPlus开发板SPI转CAN操作

飞凌嵌入式OKMX8MP-C核心板有两路原生CAN总线,但用户在开发产品时可能需要用到更多的CAN,这该如何解决呢?今天小编将为大家介绍一种SPI转CAN的方法,供各位工程师小伙伴参考。 说明 OKMX8MP-C核心板有两路原生的SPI总线&#xff0c…...

Docker中容器的随机命名方式

使用 docker 创建容器时,如果没有用 --name 指定,docker 会为用户选择一个名称, 格式是两个带有下划线的单词,如xxx_yyyy 其相关的实现在此处 pkg/namesgenerator/names-generator.go[1] 源码中有两个数组,第一个是一个…...

大数据Flink实时计算技术

1、架构 2、应用场景 Flink 功能强大,支持开发和运行多种不同种类的应用程序。它的主要特性包括:批流一体化、精密的状态管理、事件时间支持以及精确一次的状态一致性保障等。在启用高可用选项的情况下,它不存在单点失效问题。事实证明&#…...

数学中的自由与我们的生活

数学中的这些自由可以帮助我们养成很多优秀的品格。具体来说,知识的自由使我们变得足智多谋,让我们可以根据问题的具体情况选择恰当的工具和方法。探索的自由使我们在集体讨论时敢于大声发言,积极提问,让我们在为探索发现而欢呼雀…...

8 python的迭代器和生成器

概述 在上一节,我们介绍了Python的模块和包,包括:什么是模块、导入模块、自定义模块、__name__、什么是包、创建包、导入包等内容。在这一节中,我们将介绍Python的迭代器和生成器。在Python中,迭代器是一个非常重要的概…...

Git的基本使用笔记——狂神说

版本控制 版本迭代, 版本控制( Revision control)是一种在开发的过程中用于管理我们对文件、目录或工程等内容的修改历史,方便查看更改历史记录,备份以便恢复以前的版本的软件工程技术。 实现跨区域多人协同开发 追踪和记载一个或者多个文件的…...

【小程序】外部二维码扫码打开微信小程序并跳转到指定页面

外部二维码扫码打开微信小程序并跳转到指定页面 您需要使用微信提供的跳转链接和相关参数。以下是实现的步骤: 生成跳转链接:使用以下链接格式生成跳转链接,其中APPID是您的小程序的 AppID,PATH是您要跳转的页面路径&#xff0c…...

【Axure高保真原型】引导弹窗

今天和大家中分享引导弹窗的原型模板,载入页面后,会显示引导弹窗,适用于引导用户使用页面,点击完成后,会显示下一个引导弹窗,直至最后一个引导弹窗完成后进入首页。具体效果可以点击下方视频观看或打开下方…...

YSYX学习记录(八)

C语言&#xff0c;练习0&#xff1a; 先创建一个文件夹&#xff0c;我用的是物理机&#xff1a; 安装build-essential 练习1&#xff1a; 我注释掉了 #include <stdio.h> 出现下面错误 在你的文本编辑器中打开ex1文件&#xff0c;随机修改或删除一部分&#xff0c;之后…...

第25节 Node.js 断言测试

Node.js的assert模块主要用于编写程序的单元测试时使用&#xff0c;通过断言可以提早发现和排查出错误。 稳定性: 5 - 锁定 这个模块可用于应用的单元测试&#xff0c;通过 require(assert) 可以使用这个模块。 assert.fail(actual, expected, message, operator) 使用参数…...

鸿蒙DevEco Studio HarmonyOS 5跑酷小游戏实现指南

1. 项目概述 本跑酷小游戏基于鸿蒙HarmonyOS 5开发&#xff0c;使用DevEco Studio作为开发工具&#xff0c;采用Java语言实现&#xff0c;包含角色控制、障碍物生成和分数计算系统。 2. 项目结构 /src/main/java/com/example/runner/├── MainAbilitySlice.java // 主界…...

JAVA后端开发——多租户

数据隔离是多租户系统中的核心概念&#xff0c;确保一个租户&#xff08;在这个系统中可能是一个公司或一个独立的客户&#xff09;的数据对其他租户是不可见的。在 RuoYi 框架&#xff08;您当前项目所使用的基础框架&#xff09;中&#xff0c;这通常是通过在数据表中增加一个…...

GO协程(Goroutine)问题总结

在使用Go语言来编写代码时&#xff0c;遇到的一些问题总结一下 [参考文档]&#xff1a;https://www.topgoer.com/%E5%B9%B6%E5%8F%91%E7%BC%96%E7%A8%8B/goroutine.html 1. main()函数默认的Goroutine 场景再现&#xff1a; 今天在看到这个教程的时候&#xff0c;在自己的电…...

DeepSeek源码深度解析 × 华为仓颉语言编程精粹——从MoE架构到全场景开发生态

前言 在人工智能技术飞速发展的今天&#xff0c;深度学习与大模型技术已成为推动行业变革的核心驱动力&#xff0c;而高效、灵活的开发工具与编程语言则为技术创新提供了重要支撑。本书以两大前沿技术领域为核心&#xff0c;系统性地呈现了两部深度技术著作的精华&#xff1a;…...

用鸿蒙HarmonyOS5实现中国象棋小游戏的过程

下面是一个基于鸿蒙OS (HarmonyOS) 的中国象棋小游戏的实现代码。这个实现使用Java语言和鸿蒙的Ability框架。 1. 项目结构 /src/main/java/com/example/chinesechess/├── MainAbilitySlice.java // 主界面逻辑├── ChessView.java // 游戏视图和逻辑├──…...

绕过 Xcode?使用 Appuploader和主流工具实现 iOS 上架自动化

iOS 应用的发布流程一直是开发链路中最“苹果味”的环节&#xff1a;强依赖 Xcode、必须使用 macOS、各种证书和描述文件配置……对很多跨平台开发者来说&#xff0c;这一套流程并不友好。 特别是当你的项目主要在 Windows 或 Linux 下开发&#xff08;例如 Flutter、React Na…...

聚六亚甲基单胍盐酸盐市场深度解析:现状、挑战与机遇

根据 QYResearch 发布的市场报告显示&#xff0c;全球市场规模预计在 2031 年达到 9848 万美元&#xff0c;2025 - 2031 年期间年复合增长率&#xff08;CAGR&#xff09;为 3.7%。在竞争格局上&#xff0c;市场集中度较高&#xff0c;2024 年全球前十强厂商占据约 74.0% 的市场…...