785. 判断二分图
785. 判断二分图
- 原题链接:
- 完成情况:
- 解题思路:
- 参考代码:
原题链接:
785. 判断二分图
https://leetcode.cn/problems/is-graph-bipartite/description/
完成情况:

解题思路:
题目解释:每个节点都有一个编号 0~~~n-1然后一个graph[][] 二维数组,其中每个数组graph[u],代表按编号顺序过去的,里面的内容即为与当前对应编号所连接的边有哪些。
染色法 去解。
在算法中,“染色法” 通常指的是图论中的一种算法,用于解决图的染色问题,其中最经典的问题就是图的顶点着色问题。该问题的目标是为图的顶点分配颜色,使得任何相邻的顶点具有不同的颜色,同时最小化所使用的颜色数目。
这个问题在现实生活中有很多应用,例如在时间表设计中,课程或会议安排不同时需要同一时间和地点的资源,就可以使用图的染色方法来解决。
染色法有不同的变种和算法,其中一种基本的方法是贪心染色算法。贪心染色算法从一个顶点开始,为其分配一个颜色,然后遍历相邻的顶点,为每个相邻顶点分配一个颜色,但要确保分配的颜色与其相邻顶点的颜色不同。然后继续遍历未着色的顶点,为其分配颜色,并重复这个过程,直到所有顶点都被染色。
然而,贪心染色算法并不总能保证得到最少的颜色数。在一些情况下,可能需要使用更复杂的图染色算法,如回溯法、分支限界法等,来找到更优的染色方案。
总之,“染色法” 是解决图的顶点着色问题的一种算法,用于在满足相邻顶点颜色不同的条件下,找到尽可能少的颜色数目。
参考代码:
package 西湖算法题解___中等题;public class __785判断二分图__染色法 {/**题目解释:每个节点都有一个编号 0~~~n-1然后一个graph[][] 二维数组,其中每个数组graph[u],代表按编号顺序过去的,里面的内容即为与当前对应编号所连接的边有哪些。*/int color [];public boolean isBipartite(int[][] graph) {int nLength = graph.length; //这是一个无向图color = new int[nLength];boolean flag = true;for (int i=0;i<nLength;i++){if (color[i] == 0){if (!dfs_isBipartite(i,1,graph)){flag = false;}}}return flag;}/**** @param u* @param c* @param graph* @return*/private boolean dfs_isBipartite(int u, int c, int[][] graph) {color[u] = c;for (int i = 0;i<graph[u].length;i++){int node = graph[u][i];if (color[node] == 0) {if (!dfs_isBipartite(node, 3 - c, graph)) {return false;}} else {if (color[node] == c){return false;}}}return true;}
}相关文章:
785. 判断二分图
785. 判断二分图 原题链接:完成情况:解题思路:参考代码: 原题链接: 785. 判断二分图 https://leetcode.cn/problems/is-graph-bipartite/description/ 完成情况: 解题思路: 题目解释&#x…...
限时 180 天,微软为 RHEL 9 和 Ubuntu 22.04 推出 SQL Server 2022 预览评估版
导读近日消息,微软公司今天发布新闻稿,宣布面向 Red Hat Enterprise Linux(RHEL)9 和 Ubuntu 22.04 两大发行版,以预览模式推出 SQL Server 2022 评估版。 近日消息,微软公司今天发布新闻稿,宣布…...
一款ccm的功率因素校正控制器ncp1654
产品概述: NCP1654是用于连续传导模式的控制器(CCM)功率因数校正升压预转换器。它控制固定频率模式下的电源开关导通时间(PWM)并且取决于瞬时线圈电流。 该电路封装在SO8封装中,最大限度地减少了外部组件&a…...
4.若依框架上传文件
1.服务端代码-控制器 /*** 上传文件*/PostMapping("/upload")Operation(summary "上传")public AjaxResult uploadFile(MultipartFile file) throws Exception {try {// 上传文件路径String filePath RuoYiConfig.getUploadPath();// 上传并返回新文件名…...
Property ‘sqlSessionFactory‘ or ‘sqlSessionTemplate‘ are required
项目场景: 最近因为公司业务需要在搭一个新架构,用的springboot3和jdk17,在整合mybatis多数据源的时候报错 (引用的mybatisplus 和 mybatisplusjion的是最新的包-2023-08-26) Error creating bean with name ‘XXXServiceImpl’:…...
idea的debug断点的使用
添加断点(目前不知道如何添加断点,就给AutoConfigurationImportSelector的每个方法都加上断点): 然后将StockApplication启动类以debug方式运行,然后程序就会停在119行 点击上边的step over让程序往下运行一行&#x…...
【UE】蓝图通信——事件分发器
目标 比如我现在希望点击控件蓝图A中的按钮后,蓝图B能够马上做出响应 实现步骤 1. 这里控件蓝图A叫“UI_按钮”,我在该蓝图中创建了一个名为“btnIsClicked”的事件分发器 当按钮被点击时,就会调用“btnIsClicked” 2. 蓝图B这里叫做“BP_…...
Python爬虫分布式架构问题汇总
在使用Python爬虫分布式架构中可能出现以下的问题,我们针对这些问题,列出相应解决方案: 1、任务重复执行 在分布式环境下,多个爬虫节点同时从消息队列中获取任务,可能导致任务重复执行的问题。 解决方案:…...
AIGC人工智能涉及三十六职业,看看有没有你的职业(一)
文章目录 一只弹吉他的熊猫 神奇的企鹅 功夫熊猫 视觉光影下的女子 闪光灯效 局部柔光 生物光 LOGO设计 制作儿童绘本故事 换脸艺术 打造专属动漫头像 包装设计之美 建筑设计 如何转高清图 生成3D质感图标 生成微信表情包 探索美食摄影的奇妙之旅 蛋糕创意设…...
万界星空科技/免费MES系统/免费质量检测系统
质量管理也是万界星空科技免费MES中的一个重要组成部分,旨在帮助制造企业实现全面的质量管理。该系统涵盖了供应商来料、生产过程、质量检验、数据分析等各个环节,为企业提供了一站式的质量管理解决方案。 1. 实时质量监控 质量管理能够实时监控生产过程…...
解决IndexError: index 0 is out of bounds for axis 1 with size 0
标题 引言问题背景解决思路如何防止总结参考资料 博主 默语带您 Go to New World. ✍ 个人主页—— 默语 的博客👦🏻 《java 面试题大全》 🍩惟余辈才疏学浅,临摹之作或有不妥之处,还请读者海涵指正。☕🍭…...
Java中hashTable的基本介绍,细节讨论,使用注意事项,常用方法和底层的扩容机制
Hashtable 是 Java 标准库中提供的一个古老的散列表(Hash Table)实现,用于存储键值对。它是线程安全的,基于哈希表的数据结构。然而,由于其线程安全性引入的同步机制,使得在多线程环境下性能相对较低。在现…...
redis -实战记录
redis -实战记录 一、安装二、使用 一、安装 centos - docker安装redisWindows10安装redis(图文教程) 二、使用 node-red进行读写redis...
Mysql知识梳理
Mysql知识梳理 索引索引分类索引未命中的原因性能调优命令Explain回表 mysql性能优化事务四大特性事务隔离级别设置事务隔离级别 存储引擎聚簇索引和非聚簇索引聚簇索引非聚簇索引 最左前缀结合原则全文索引 索引 索引分类 mysql有普通索引、空间索引、主键索引、唯一索引、组…...
文生图模型之Stable Diffusion
原始文章地址 autoencoder CLIP text encoder tokenizer最大长度为77(CLIP训练时所采用的设置),当输入text的tokens数量超过77后,将进行截断,如果不足则进行paddings,这样将保证无论输入任何长度的文本&…...
Java List循环安全删除元素
Java List循环安全删除元素的几种方式如下: 使用迭代器(Iterator):通过调用List的iterator()方法获取List的迭代器,然后使用迭代器的remove()方法删除元素。这种方式可以避免在遍历过程中修改List导致的并发修改异常&…...
2023年03月 C/C++(三级)真题解析#中国电子学会#全国青少年软件编程等级考试
第1题:和数 给定一个正整数序列,判断其中有多少个数,等于数列中其他两个数的和。 比如,对于数列1 2 3 4, 这个问题的答案就是2, 因为3 = 2 + 1, 4 = 1 + 3。 时间限制:10000 内存限制:65536 输入 共两行,第一行是数列中数的个数n ( 1 <= n <= 100),第二行是由n个…...
bert-base-chinese 判断上下句
利用BERT等模型来实现语义分割。BERT等模型在预训练的时候采用了NSP(next sentence prediction)的训练任务,因此BERT完全可以判断两个句子(段落)是否具有语义衔接关系。这里我们可以设置相似度阈值 MERGE_RATIO &#…...
vue3+vue-cli使用mockjs
1.下载mockjs包 npm i mockjs -D 2.main.js中全局引入 // mock模拟后端数据 import /mock/index.js 3.axios下baseUrl注释掉,让其不走本地代理 // 使用mock数据的话,将这一项注释即可 // axios.defaults.baseURL process.env.VUE_APP_BASE_API; 4.s…...
Android 全局监听软键盘弹起隐藏 动态修改布局并适配无限循环的问题
思路: 要在 Android 应用中全局检测软键盘的弹起,您可以使用 ViewTreeObserver.OnGlobalLayoutListener 监听器来监听布局树的变化。当软键盘弹起或隐藏时,布局树会发生变化,因此您可以在监听器中捕获这些变化。 以下是一个示例…...
Zig语言构建工具zcc详解:依赖管理与项目构建实践
1. 项目概述:一个为Zig语言量身打造的构建系统最近在折腾Zig语言项目时,发现了一个挺有意思的工具:git-on-my-level/zcc。乍一看这个名字,可能会让人联想到经典的C编译器gcc,或者猜测它是一个Zig语言的C编译器前端。但…...
PADS PCB设计工具的核心优势与应用实践
1. PADS PCB设计工具概述作为一名拥有十年PCB设计经验的工程师,我亲身体验过从Protel到Altium再到Cadence Allegro的各种EDA工具。但当我在2015年首次接触PADS时,它独特的"约束驱动设计"理念和高效的交互式布线引擎立刻吸引了我。PADS…...
VS Code 修改 C++ 标准同时修改错误检测标准
修改C标准基于使用Code Running拓展 可以看我上一章文章 VS Code 整洁的打印内容到终端https://blog.csdn.net/2301_76542477/article/details/161060041?sharetypeblogdetail&sharerId161060041&sharereferPC&sharesource2301_76542477&spm1011.2480.3001.…...
Zynq平台实战:为Linux内核打上Preempt-RT实时补丁
1. 为什么Zynq需要实时Linux内核? 在工业控制、机器人、医疗设备等对时序要求严格的领域,毫秒级的延迟都可能导致灾难性后果。Xilinx Zynq-7000这类异构SoC虽然集成了ARM处理器和FPGA,但标准Linux内核的完全公平调度器(CFS&#x…...
嵌入式实战:STM32智能温度控制系统的算法优化与工程实现
嵌入式实战:STM32智能温度控制系统的算法优化与工程实现 【免费下载链接】STM32 项目地址: https://gitcode.com/gh_mirrors/stm322/STM32 在工业自动化、医疗设备和智能家居领域,温度控制系统的精度和稳定性直接影响着设备性能和用户体验。传统…...
2026最权威的五大降AI率网站横评
Ai论文网站排名(开题报告、文献综述、降aigc率、降重综合对比) TOP1. 千笔AI TOP2. aipasspaper TOP3. 清北论文 TOP4. 豆包 TOP5. kimi TOP6. deepseek 于当下学术研究的语境里,AI论文工具有着强大功能,可全面涵盖文献梳理…...
告别虚拟机卡顿:在Proxmox VE 7.0上丝滑安装中兴新支点NewStartOS 4.3.8社区版
告别虚拟机卡顿:在Proxmox VE 7.0上丝滑安装中兴新支点NewStartOS 4.3.8社区版 虚拟化技术已成为现代IT基础设施的核心组件,而Proxmox VE作为开源的虚拟化管理平台,凭借其稳定性和灵活性赢得了众多技术团队的青睐。在众多虚拟化应用场景中&am…...
Xilinx 7系列FPGA目标设计平台:从芯片到生态的系统开发革命
1. 项目概述:Xilinx 7系列FPGA设计平台的划时代意义作为一名在数字系统设计领域摸爬滚打了十几年的工程师,我至今还记得2012年初听到Xilinx发布其28nm 7系列FPGA首批“目标设计平台”时的兴奋感。那感觉就像是,一直需要自己从零开始搭积木、焊…...
【C++ AI 大模型接入 SDK】 - 项目介绍与 AI 知识科普
大家好,我是Halcyon.平安 欢迎文末添加好友交流,共同进步! 一、项目介绍核心功能二、AI 基础知识科普2.1 什么是大语言模型(LLM)2.2 API 调用方式2.3 全量响应 vs 流式响应2.4 SSE(Server-Sent Events&…...
Node.js 服务端项目如何集成 Taotoken 实现稳定大模型调用
🚀 告别海外账号与网络限制!稳定直连全球优质大模型,限时半价接入中。 👉 点击领取海量免费额度 Node.js 服务端项目如何集成 Taotoken 实现稳定大模型调用 在构建现代服务端应用时,集成大模型能力已成为提升产品智能…...
