【算法基础:搜索与图论】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架构-微服务 单体架构及其所面临的问题 在互联网发展初期,用户数量少,流量小,硬件成本高。因此…...
AI-调查研究-01-正念冥想有用吗?对健康的影响及科学指南
点一下关注吧!!!非常感谢!!持续更新!!! 🚀 AI篇持续更新中!(长期更新) 目前2025年06月05日更新到: AI炼丹日志-28 - Aud…...
React 第五十五节 Router 中 useAsyncError的使用详解
前言 useAsyncError 是 React Router v6.4 引入的一个钩子,用于处理异步操作(如数据加载)中的错误。下面我将详细解释其用途并提供代码示例。 一、useAsyncError 用途 处理异步错误:捕获在 loader 或 action 中发生的异步错误替…...
云原生核心技术 (7/12): K8s 核心概念白话解读(上):Pod 和 Deployment 究竟是什么?
大家好,欢迎来到《云原生核心技术》系列的第七篇! 在上一篇,我们成功地使用 Minikube 或 kind 在自己的电脑上搭建起了一个迷你但功能完备的 Kubernetes 集群。现在,我们就像一个拥有了一块崭新数字土地的农场主,是时…...
椭圆曲线密码学(ECC)
一、ECC算法概述 椭圆曲线密码学(Elliptic Curve Cryptography)是基于椭圆曲线数学理论的公钥密码系统,由Neal Koblitz和Victor Miller在1985年独立提出。相比RSA,ECC在相同安全强度下密钥更短(256位ECC ≈ 3072位RSA…...
Unity3D中Gfx.WaitForPresent优化方案
前言 在Unity中,Gfx.WaitForPresent占用CPU过高通常表示主线程在等待GPU完成渲染(即CPU被阻塞),这表明存在GPU瓶颈或垂直同步/帧率设置问题。以下是系统的优化方案: 对惹,这里有一个游戏开发交流小组&…...
在rocky linux 9.5上在线安装 docker
前面是指南,后面是日志 sudo dnf config-manager --add-repo https://download.docker.com/linux/centos/docker-ce.repo sudo dnf install docker-ce docker-ce-cli containerd.io -y docker version sudo systemctl start docker sudo systemctl status docker …...
自然语言处理——Transformer
自然语言处理——Transformer 自注意力机制多头注意力机制Transformer 虽然循环神经网络可以对具有序列特性的数据非常有效,它能挖掘数据中的时序信息以及语义信息,但是它有一个很大的缺陷——很难并行化。 我们可以考虑用CNN来替代RNN,但是…...
Java毕业设计:WML信息查询与后端信息发布系统开发
JAVAWML信息查询与后端信息发布系统实现 一、系统概述 本系统基于Java和WML(无线标记语言)技术开发,实现了移动设备上的信息查询与后端信息发布功能。系统采用B/S架构,服务器端使用Java Servlet处理请求,数据库采用MySQL存储信息࿰…...
DiscuzX3.5发帖json api
参考文章:PHP实现独立Discuz站外发帖(直连操作数据库)_discuz 发帖api-CSDN博客 简单改造了一下,适配我自己的需求 有一个站点存在多个采集站,我想通过主站拿标题,采集站拿内容 使用到的sql如下 CREATE TABLE pre_forum_post_…...
DAY 26 函数专题1
函数定义与参数知识点回顾:1. 函数的定义2. 变量作用域:局部变量和全局变量3. 函数的参数类型:位置参数、默认参数、不定参数4. 传递参数的手段:关键词参数5 题目1:计算圆的面积 任务: 编写一…...
