【算法基础:搜索与图论】3.6 二分图(染色法判定二分图匈牙利算法)
文章目录
- 二分图介绍
- 染色法判定二分图
- 例题:860. 染色法判定二分图
- 匈牙利匹配
- 二分图最大匹配
- 匈牙利匹配算法思想
- 例题:861. 二分图的最大匹配
二分图介绍
https://oi-wiki.org/graph/bi-graph/
二分图是图论中的一个概念,它的所有节点可以被分为两个独立的集合,每个边的两个端点分别来自这两个不同的集合。
换句话说,二分图中不存在连接同一集合内两个节点的边。


染色法判定二分图
如何判断一个图是二分图?
当且仅当图中不含奇数环。(奇数环指的是环中边的个数是奇数)(因为每一条边都是从一个集合走到另一个集合,只有走偶数次才有可能回到同一个集合。)
染色:相邻的节点的颜色不一样。

因为没有奇数环,所以染色过程是一定不会发生矛盾的。
时间复杂度是 O ( n + m ) O(n + m) O(n+m) , n 表示点数,m 表示边数。
例题:860. 染色法判定二分图
https://www.acwing.com/activity/content/problem/content/926/

使用 dfs 对图中各个节点染色,染色过程中不发生冲突即为二分图。
import java.util.*;public class Main {static final int N = 100005;static List<Integer>[] g = new ArrayList[N];static int[] color = new int[N];public static void main(String[] args){Scanner sc = new Scanner(System.in);int n = sc.nextInt(), m = sc.nextInt();// 建图Arrays.setAll(g, e -> new ArrayList<Integer>());for (int i = 0; i < m; ++i) {int u = sc.nextInt(), v = sc.nextInt();g[u].add(v);g[v].add(u);}// 图可能由多个非连通的子图构成。因此,应该对每一个尚未访问过的点都进行一次深度优先搜索。boolean f = true;for (int i = 1; i <= n; ++i) {if (color[i] == 0 && !dfs(i, 1)) {f = false;break;}}System.out.println(f? "Yes": "No");}static boolean dfs(int x, int c) {boolean res = true;color[x] = c;for (int y: g[x]) {if (color[y] == 0) res &= dfs(y, 3 - c);else if (color[y] == color[x]) return false;}return res;}
}
匈牙利匹配
二分图最大匹配
**二分图最大匹配**:
翻译成人话就是——
给定一个二分图 G,即分左右两部分,各部分之间的点没有边连接,要求选出一些边,使得这些边没有公共顶点,且边的数量最大。
匈牙利匹配算法思想
两个集合的点数分别是 n1 , n2。
枚举 n1 , 尝试 i 是否可以找到一个 j 完成匹配,匹配成功就 ++cnt。
所以重点是 find(i) 方法:
对每个 i ,枚举 i 相邻的所有 j —— 如果 j 没有被匹配就直接返回 true;如果 j 被匹配了,就尝试现在和 j 匹配的另一个 i 能不能换一个 j,能换就换一个然后返回 true;否则返回 false。
时间复杂度是 O ( n ∗ m ) O(n * m) O(n∗m),n 表示点数,m 表示边数。
例题:861. 二分图的最大匹配
https://www.acwing.com/activity/content/problem/content/927/

重点是理解数组 match 和 st 的含义,以及方法 find(x) 的写法和使用。
import java.util.*;public class Main {static final int N = 505;static int[][] g = new int[N][N];static int[] match = new int[N]; // match记录集合2中各个点匹配的集合1的点是哪个static boolean[] st = new boolean[N]; // st表示集合2中的点有没有被匹配static int n1, n2;public static void main(String[] args){Scanner sc = new Scanner(System.in);n1 = sc.nextInt();n2 = sc.nextInt();int m = sc.nextInt();// 建图for (int i = 0; i < m; ++i) {int u = sc.nextInt(), v = sc.nextInt();g[u][v] = 1; // 左边的 u 和 右边的 v 之间有一条边}int cnt = 0;for (int i = 1; i <= n1; ++i) {Arrays.fill(st, false); // 重置stif (find(i)) ++cnt;}System.out.println(cnt);}static boolean find(int x) {for (int j = 1; j <= n2; ++j) {if (!st[j] && g[x][j] == 1) {st[j] = true;// 如果 j 还没有匹配或者当前使用 j 的 x 可以让出去if (match[j] == 0 || find(match[j])) {match[j] = x;return true;}}}return false;}
}相关文章:
【算法基础:搜索与图论】3.6 二分图(染色法判定二分图匈牙利算法)
文章目录 二分图介绍染色法判定二分图例题:860. 染色法判定二分图 匈牙利匹配二分图最大匹配匈牙利匹配算法思想例题:861. 二分图的最大匹配 二分图介绍 https://oi-wiki.org/graph/bi-graph/ 二分图是图论中的一个概念,它的所有节点可以被…...
SpringMVC 怎么和 AJAX 相互调用的
通过 Jackson 框架就可以把 Java 里面的对象直接转化成 Js 可以识别的 Json 对象。 步骤如下 : a、加入 Jackson.jar b、在配置文件中配置 json 的映射 c、在接受 Ajax 方法里面可以直接返回 Object,List 等,但方法前面要加上ResponseBody 详细步骤: …...
UCDOS和WPS推动计算机领域的汉字化发展,中文编程该谁力扛大旗?
你还记得UCDOS吗? 从DOS时代过来的人,还知道UCDOS的,现在可能已经是中年人了! 当时,鲍岳桥的UCDOS可以称得上是中国的国产操作系统。 在Windows还没来得及进入中国市场时,UCDOS可以说是走向了巅峰时刻&a…...
golang+layui提升界面美化度--[推荐]
一、背景 golanglayui提升界面美化度--[推荐]; golang后端写的页面很难看,如何好看点呢,那就是layui https://layui.dev/ 也是一个简单上手容易使用的框架,类似jquery,对于后端开发来说满足使用需求 二、使用注意点…...
42. 接雨水
题目介绍 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。 示例 1: 输入:height [0,1,0,2,1,0,1,3,2,1,2,1] 输出:6 解释:上面是由数组 [0,1,0,2,1,0,1,3…...
Python学习阶段路线和内容
Python学习阶段路线和内容 这是我的看法和认识,供参考。 Python学习路线主要分为三个阶段:入门阶段、提高阶段和深入阶段。 入门阶段 入门阶段需要学习Python的基本语法,掌握变量和数据类型、条件语句和循环语句、函数和模块等内容。并通过…...
RocketMQ教程-安装和配置
Linux系统安装配置 64位操作系统,推荐 Linux/Unix/macOS 64位 JDK 1.8 Maven3.0 yum 安装jdk8 yum 安装maven 1.下载安装Apache RocketMQ RocketMQ 的安装包分为两种,二进制包和源码包。 点击这里 下载 Apache RocketMQ 5.1.3的源码包。你也可以从这…...
【LeetCode】55.跳跃游戏
题目 给定一个非负整数数组 nums ,你最初位于数组的 第一个下标 。 数组中的每个元素代表你在该位置可以跳跃的最大长度。 判断你是否能够到达最后一个下标。 示例 1: 输入:nums [2,3,1,1,4] 输出:true 解释:可以…...
Docker学习路线12:开发者体验
到目前为止,我们只讨论了使用Docker来部署应用程序。然而,Docker也是一个极好的用于开发应用程序的工具。可以采用一些不同的建议来改善开发体验。 在应用程序中使用docker-compose以方便开发。使用绑定挂载将本地代码挂载到容器文件系统中,…...
后端服务迁移方案及过程记录
阶段时序动作双写数据对比1新rdb集群上线双写数据对比2新服务上线,无流量双写数据对比2后端自己发起的流程比如job,新服务上线一份新的,独立运行双写数据对比2消费二方mq,新服务使用新的消费组消费原有消息双写数据对比3新旧服务比…...
StAX解析
StAX解析 StAX解析介绍 StAX解析与SAX解析类似,也是基于事件驱动的,不同之处在于StAX采用的是拉模式,应用程序通过调用解析器推进解析的进程,可以调用next()方法来获取下一个解析事件(开始文档,结束文档,开…...
[MCU]AUTOSAR COM STACK - CAN协议栈
各层PDU PDU:Protocal Data Unit,协议数据单元,由SDU和PCI组成; I-PDU:Interaction Layer PDU,数据交互层PDU;N-PDU:NetWork Layer PDU,网络层PDU,通常用的…...
React:从 npx开始
使用 npm 来创建第一个 recat 文件( react-demo 是文件名,可以自定义) npx create-react-app react-demo npx是 npm v5.2 版本新添加的命令,用来简化 npm 中工具包的使用 原始: 全局安装npm i -g create-react-app 2 …...
力扣热门100题之接雨水【困难】
题目描述 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。 示例 1: 输入:height [0,1,0,2,1,0,1,3,2,1,2,1] 输出:6 解释:上面是由数组 [0,1,0,2,1,0,1,3…...
Stable-Diffusion-Webui部署SDXL0.9报错参数shape不匹配解决
问题 已经在model/stable-diffusion文件夹下放进去了sdxl0.9的safetensor文件,但是在切换model的时候,会报错model的shape不一致。 解决方法 git pullupdate一些web-ui项目就可以,因为当前项目太老了,没有使用最新的版本。...
Springboot @Async 多线程获取返回值
Springboot Async 多线程获取返回值 需求背景 最近需要用到多线程, 自己维护线程池很麻烦, 正好看到Springboot集成线程池的例子, 这里自己做了个尝试和总结, 记录一下, 也分享给需要的朋友; 不考虑事务的情况下, 这个多线程实现比较简单, 主要有以下几点: 在启动类加上Enab…...
怎样接入chatGPT
官网链接: OpenAI platform...
Docker consul容器服务更新与发现
Docker consul容器服务更新与发现 一、什么事服务注册与发现二、什么是consul三、consul部署1、consul服务器2、registrator服务器3、consul-template 一、什么事服务注册与发现 服务注册与发现是微服务架构中不可或缺的重要组件。起初服务都是单节点的,不保障高可…...
[算法很美打卡] 多维数组篇 (打卡第一天)
文章目录 顺时针打印二维数组0所在的行列清零 顺时针打印二维数组 package 每日算法学习打卡.算法打卡.七月份.七月二十六号;public class test1 {public static void main(String[] args) {int[][] matrix {{1,2},{5,6},{9,10},{13,14},};print(matrix);}static void print(i…...
微服务系列(1)-who i am?
微服务系列(1)-我是谁 应用架构的演化 简单来说系统架构可以分为以下几个阶段:复杂的臃肿的单体架构-SOA架构-微服务 单体架构及其所面临的问题 在互联网发展初期,用户数量少,流量小,硬件成本高。因此…...
观成科技:隐蔽隧道工具Ligolo-ng加密流量分析
1.工具介绍 Ligolo-ng是一款由go编写的高效隧道工具,该工具基于TUN接口实现其功能,利用反向TCP/TLS连接建立一条隐蔽的通信信道,支持使用Let’s Encrypt自动生成证书。Ligolo-ng的通信隐蔽性体现在其支持多种连接方式,适应复杂网…...
网络六边形受到攻击
大家读完觉得有帮助记得关注和点赞!!! 抽象 现代智能交通系统 (ITS) 的一个关键要求是能够以安全、可靠和匿名的方式从互联车辆和移动设备收集地理参考数据。Nexagon 协议建立在 IETF 定位器/ID 分离协议 (…...
简易版抽奖活动的设计技术方案
1.前言 本技术方案旨在设计一套完整且可靠的抽奖活动逻辑,确保抽奖活动能够公平、公正、公开地进行,同时满足高并发访问、数据安全存储与高效处理等需求,为用户提供流畅的抽奖体验,助力业务顺利开展。本方案将涵盖抽奖活动的整体架构设计、核心流程逻辑、关键功能实现以及…...
《从零掌握MIPI CSI-2: 协议精解与FPGA摄像头开发实战》-- CSI-2 协议详细解析 (一)
CSI-2 协议详细解析 (一) 1. CSI-2层定义(CSI-2 Layer Definitions) 分层结构 :CSI-2协议分为6层: 物理层(PHY Layer) : 定义电气特性、时钟机制和传输介质(导线&#…...
1.3 VSCode安装与环境配置
进入网址Visual Studio Code - Code Editing. Redefined下载.deb文件,然后打开终端,进入下载文件夹,键入命令 sudo dpkg -i code_1.100.3-1748872405_amd64.deb 在终端键入命令code即启动vscode 需要安装插件列表 1.Chinese简化 2.ros …...
C# SqlSugar:依赖注入与仓储模式实践
C# SqlSugar:依赖注入与仓储模式实践 在 C# 的应用开发中,数据库操作是必不可少的环节。为了让数据访问层更加简洁、高效且易于维护,许多开发者会选择成熟的 ORM(对象关系映射)框架,SqlSugar 就是其中备受…...
【论文阅读28】-CNN-BiLSTM-Attention-(2024)
本文把滑坡位移序列拆开、筛优质因子,再用 CNN-BiLSTM-Attention 来动态预测每个子序列,最后重构出总位移,预测效果超越传统模型。 文章目录 1 引言2 方法2.1 位移时间序列加性模型2.2 变分模态分解 (VMD) 具体步骤2.3.1 样本熵(S…...
【碎碎念】宝可梦 Mesh GO : 基于MESH网络的口袋妖怪 宝可梦GO游戏自组网系统
目录 游戏说明《宝可梦 Mesh GO》 —— 局域宝可梦探索Pokmon GO 类游戏核心理念应用场景Mesh 特性 宝可梦玩法融合设计游戏构想要素1. 地图探索(基于物理空间 广播范围)2. 野生宝可梦生成与广播3. 对战系统4. 道具与通信5. 延伸玩法 安全性设计 技术选…...
是否存在路径(FIFOBB算法)
题目描述 一个具有 n 个顶点e条边的无向图,该图顶点的编号依次为0到n-1且不存在顶点与自身相连的边。请使用FIFOBB算法编写程序,确定是否存在从顶点 source到顶点 destination的路径。 输入 第一行两个整数,分别表示n 和 e 的值(1…...
JVM虚拟机:内存结构、垃圾回收、性能优化
1、JVM虚拟机的简介 Java 虚拟机(Java Virtual Machine 简称:JVM)是运行所有 Java 程序的抽象计算机,是 Java 语言的运行环境,实现了 Java 程序的跨平台特性。JVM 屏蔽了与具体操作系统平台相关的信息,使得 Java 程序只需生成在 JVM 上运行的目标代码(字节码),就可以…...
