可能的二分法 -- 二分图判定【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开放平台的开发者…...

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总线,…...
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是您要跳转的页面路径,…...

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

YSYX学习记录(八)
C语言,练习0: 先创建一个文件夹,我用的是物理机: 安装build-essential 练习1: 我注释掉了 #include <stdio.h> 出现下面错误 在你的文本编辑器中打开ex1文件,随机修改或删除一部分,之后…...
第25节 Node.js 断言测试
Node.js的assert模块主要用于编写程序的单元测试时使用,通过断言可以提早发现和排查出错误。 稳定性: 5 - 锁定 这个模块可用于应用的单元测试,通过 require(assert) 可以使用这个模块。 assert.fail(actual, expected, message, operator) 使用参数…...
鸿蒙DevEco Studio HarmonyOS 5跑酷小游戏实现指南
1. 项目概述 本跑酷小游戏基于鸿蒙HarmonyOS 5开发,使用DevEco Studio作为开发工具,采用Java语言实现,包含角色控制、障碍物生成和分数计算系统。 2. 项目结构 /src/main/java/com/example/runner/├── MainAbilitySlice.java // 主界…...
JAVA后端开发——多租户
数据隔离是多租户系统中的核心概念,确保一个租户(在这个系统中可能是一个公司或一个独立的客户)的数据对其他租户是不可见的。在 RuoYi 框架(您当前项目所使用的基础框架)中,这通常是通过在数据表中增加一个…...

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

DeepSeek源码深度解析 × 华为仓颉语言编程精粹——从MoE架构到全场景开发生态
前言 在人工智能技术飞速发展的今天,深度学习与大模型技术已成为推动行业变革的核心驱动力,而高效、灵活的开发工具与编程语言则为技术创新提供了重要支撑。本书以两大前沿技术领域为核心,系统性地呈现了两部深度技术著作的精华:…...
用鸿蒙HarmonyOS5实现中国象棋小游戏的过程
下面是一个基于鸿蒙OS (HarmonyOS) 的中国象棋小游戏的实现代码。这个实现使用Java语言和鸿蒙的Ability框架。 1. 项目结构 /src/main/java/com/example/chinesechess/├── MainAbilitySlice.java // 主界面逻辑├── ChessView.java // 游戏视图和逻辑├──…...
绕过 Xcode?使用 Appuploader和主流工具实现 iOS 上架自动化
iOS 应用的发布流程一直是开发链路中最“苹果味”的环节:强依赖 Xcode、必须使用 macOS、各种证书和描述文件配置……对很多跨平台开发者来说,这一套流程并不友好。 特别是当你的项目主要在 Windows 或 Linux 下开发(例如 Flutter、React Na…...

聚六亚甲基单胍盐酸盐市场深度解析:现状、挑战与机遇
根据 QYResearch 发布的市场报告显示,全球市场规模预计在 2031 年达到 9848 万美元,2025 - 2031 年期间年复合增长率(CAGR)为 3.7%。在竞争格局上,市场集中度较高,2024 年全球前十强厂商占据约 74.0% 的市场…...