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

【算法基础:搜索与图论】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(nm),n 表示点数,m 表示边数。

例题:861. 二分图的最大匹配

https://www.acwing.com/activity/content/problem/content/927/
在这里插入图片描述

重点是理解数组 matchst 的含义,以及方法 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 二分图(染色法判定二分图匈牙利算法)

文章目录 二分图介绍染色法判定二分图例题&#xff1a;860. 染色法判定二分图 匈牙利匹配二分图最大匹配匈牙利匹配算法思想例题&#xff1a;861. 二分图的最大匹配 二分图介绍 https://oi-wiki.org/graph/bi-graph/ 二分图是图论中的一个概念&#xff0c;它的所有节点可以被…...

SpringMVC 怎么和 AJAX 相互调用的

通过 Jackson 框架就可以把 Java 里面的对象直接转化成 Js 可以识别的 Json 对象。 步骤如下 &#xff1a; a、加入 Jackson.jar b、在配置文件中配置 json 的映射 c、在接受 Ajax 方法里面可以直接返回 Object,List 等,但方法前面要加上ResponseBody 详细步骤&#xff1a; …...

UCDOS和WPS推动计算机领域的汉字化发展,中文编程该谁力扛大旗?

你还记得UCDOS吗&#xff1f; 从DOS时代过来的人&#xff0c;还知道UCDOS的&#xff0c;现在可能已经是中年人了&#xff01; 当时&#xff0c;鲍岳桥的UCDOS可以称得上是中国的国产操作系统。 在Windows还没来得及进入中国市场时&#xff0c;UCDOS可以说是走向了巅峰时刻&a…...

golang+layui提升界面美化度--[推荐]

一、背景 golanglayui提升界面美化度--[推荐]&#xff1b; golang后端写的页面很难看&#xff0c;如何好看点呢&#xff0c;那就是layui https://layui.dev/ 也是一个简单上手容易使用的框架&#xff0c;类似jquery&#xff0c;对于后端开发来说满足使用需求 二、使用注意点…...

42. 接雨水

题目介绍 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图&#xff0c;计算按此排列的柱子&#xff0c;下雨之后能接多少雨水。 示例 1&#xff1a; 输入&#xff1a;height [0,1,0,2,1,0,1,3,2,1,2,1] 输出&#xff1a;6 解释&#xff1a;上面是由数组 [0,1,0,2,1,0,1,3…...

Python学习阶段路线和内容

Python学习阶段路线和内容 这是我的看法和认识&#xff0c;供参考。 Python学习路线主要分为三个阶段&#xff1a;入门阶段、提高阶段和深入阶段。 入门阶段 入门阶段需要学习Python的基本语法&#xff0c;掌握变量和数据类型、条件语句和循环语句、函数和模块等内容。并通过…...

RocketMQ教程-安装和配置

Linux系统安装配置 64位操作系统&#xff0c;推荐 Linux/Unix/macOS 64位 JDK 1.8 Maven3.0 yum 安装jdk8 yum 安装maven 1.下载安装Apache RocketMQ RocketMQ 的安装包分为两种&#xff0c;二进制包和源码包。 点击这里 下载 Apache RocketMQ 5.1.3的源码包。你也可以从这…...

【LeetCode】55.跳跃游戏

题目 给定一个非负整数数组 nums &#xff0c;你最初位于数组的 第一个下标 。 数组中的每个元素代表你在该位置可以跳跃的最大长度。 判断你是否能够到达最后一个下标。 示例 1&#xff1a; 输入&#xff1a;nums [2,3,1,1,4] 输出&#xff1a;true 解释&#xff1a;可以…...

Docker学习路线12:开发者体验

到目前为止&#xff0c;我们只讨论了使用Docker来部署应用程序。然而&#xff0c;Docker也是一个极好的用于开发应用程序的工具。可以采用一些不同的建议来改善开发体验。 在应用程序中使用docker-compose以方便开发。使用绑定挂载将本地代码挂载到容器文件系统中&#xff0c;…...

后端服务迁移方案及过程记录

阶段时序动作双写数据对比1新rdb集群上线双写数据对比2新服务上线&#xff0c;无流量双写数据对比2后端自己发起的流程比如job&#xff0c;新服务上线一份新的&#xff0c;独立运行双写数据对比2消费二方mq&#xff0c;新服务使用新的消费组消费原有消息双写数据对比3新旧服务比…...

StAX解析

StAX解析 StAX解析介绍 StAX解析与SAX解析类似&#xff0c;也是基于事件驱动的&#xff0c;不同之处在于StAX采用的是拉模式&#xff0c;应用程序通过调用解析器推进解析的进程&#xff0c;可以调用next()方法来获取下一个解析事件(开始文档&#xff0c;结束文档&#xff0c;开…...

[MCU]AUTOSAR COM STACK - CAN协议栈

各层PDU PDU&#xff1a;Protocal Data Unit&#xff0c;协议数据单元&#xff0c;由SDU和PCI组成&#xff1b; I-PDU&#xff1a;Interaction Layer PDU&#xff0c;数据交互层PDU&#xff1b;N-PDU&#xff1a;NetWork Layer PDU&#xff0c;网络层PDU&#xff0c;通常用的…...

React:从 npx开始

使用 npm 来创建第一个 recat 文件&#xff08; react-demo 是文件名&#xff0c;可以自定义&#xff09; npx create-react-app react-demo npx是 npm v5.2 版本新添加的命令&#xff0c;用来简化 npm 中工具包的使用 原始&#xff1a; 全局安装npm i -g create-react-app 2 …...

力扣热门100题之接雨水【困难】

题目描述 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图&#xff0c;计算按此排列的柱子&#xff0c;下雨之后能接多少雨水。 示例 1&#xff1a; 输入&#xff1a;height [0,1,0,2,1,0,1,3,2,1,2,1] 输出&#xff1a;6 解释&#xff1a;上面是由数组 [0,1,0,2,1,0,1,3…...

Stable-Diffusion-Webui部署SDXL0.9报错参数shape不匹配解决

问题 已经在model/stable-diffusion文件夹下放进去了sdxl0.9的safetensor文件&#xff0c;但是在切换model的时候&#xff0c;会报错model的shape不一致。 解决方法 git pullupdate一些web-ui项目就可以&#xff0c;因为当前项目太老了&#xff0c;没有使用最新的版本。...

Springboot @Async 多线程获取返回值

Springboot Async 多线程获取返回值 需求背景 最近需要用到多线程, 自己维护线程池很麻烦, 正好看到Springboot集成线程池的例子, 这里自己做了个尝试和总结, 记录一下, 也分享给需要的朋友; 不考虑事务的情况下, 这个多线程实现比较简单, 主要有以下几点: 在启动类加上Enab…...

怎样接入chatGPT

官网链接&#xff1a; OpenAI platform...

Docker consul容器服务更新与发现

Docker consul容器服务更新与发现 一、什么事服务注册与发现二、什么是consul三、consul部署1、consul服务器2、registrator服务器3、consul-template 一、什么事服务注册与发现 服务注册与发现是微服务架构中不可或缺的重要组件。起初服务都是单节点的&#xff0c;不保障高可…...

[算法很美打卡] 多维数组篇 (打卡第一天)

文章目录 顺时针打印二维数组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?

微服务系列&#xff08;1&#xff09;-我是谁 应用架构的演化 简单来说系统架构可以分为以下几个阶段&#xff1a;复杂的臃肿的单体架构-SOA架构-微服务 单体架构及其所面临的问题 在互联网发展初期&#xff0c;用户数量少&#xff0c;流量小&#xff0c;硬件成本高。因此…...

前端倒计时误差!

提示:记录工作中遇到的需求及解决办法 文章目录 前言一、误差从何而来?二、五大解决方案1. 动态校准法(基础版)2. Web Worker 计时3. 服务器时间同步4. Performance API 高精度计时5. 页面可见性API优化三、生产环境最佳实践四、终极解决方案架构前言 前几天听说公司某个项…...

抖音增长新引擎:品融电商,一站式全案代运营领跑者

抖音增长新引擎&#xff1a;品融电商&#xff0c;一站式全案代运营领跑者 在抖音这个日活超7亿的流量汪洋中&#xff0c;品牌如何破浪前行&#xff1f;自建团队成本高、效果难控&#xff1b;碎片化运营又难成合力——这正是许多企业面临的增长困局。品融电商以「抖音全案代运营…...

Unit 1 深度强化学习简介

Deep RL Course ——Unit 1 Introduction 从理论和实践层面深入学习深度强化学习。学会使用知名的深度强化学习库&#xff0c;例如 Stable Baselines3、RL Baselines3 Zoo、Sample Factory 和 CleanRL。在独特的环境中训练智能体&#xff0c;比如 SnowballFight、Huggy the Do…...

dify打造数据可视化图表

一、概述 在日常工作和学习中&#xff0c;我们经常需要和数据打交道。无论是分析报告、项目展示&#xff0c;还是简单的数据洞察&#xff0c;一个清晰直观的图表&#xff0c;往往能胜过千言万语。 一款能让数据可视化变得超级简单的 MCP Server&#xff0c;由蚂蚁集团 AntV 团队…...

安卓基础(aar)

重新设置java21的环境&#xff0c;临时设置 $env:JAVA_HOME "D:\Android Studio\jbr" 查看当前环境变量 JAVA_HOME 的值 echo $env:JAVA_HOME 构建ARR文件 ./gradlew :private-lib:assembleRelease 目录是这样的&#xff1a; MyApp/ ├── app/ …...

SQL慢可能是触发了ring buffer

简介 最近在进行 postgresql 性能排查的时候,发现 PG 在某一个时间并行执行的 SQL 变得特别慢。最后通过监控监观察到并行发起得时间 buffers_alloc 就急速上升,且低水位伴随在整个慢 SQL,一直是 buferIO 的等待事件,此时也没有其他会话的争抢。SQL 虽然不是高效 SQL ,但…...

虚拟电厂发展三大趋势:市场化、技术主导、车网互联

市场化&#xff1a;从政策驱动到多元盈利 政策全面赋能 2025年4月&#xff0c;国家发改委、能源局发布《关于加快推进虚拟电厂发展的指导意见》&#xff0c;首次明确虚拟电厂为“独立市场主体”&#xff0c;提出硬性目标&#xff1a;2027年全国调节能力≥2000万千瓦&#xff0…...

省略号和可变参数模板

本文主要介绍如何展开可变参数的参数包 1.C语言的va_list展开可变参数 #include <iostream> #include <cstdarg>void printNumbers(int count, ...) {// 声明va_list类型的变量va_list args;// 使用va_start将可变参数写入变量argsva_start(args, count);for (in…...

uniapp 实现腾讯云IM群文件上传下载功能

UniApp 集成腾讯云IM实现群文件上传下载功能全攻略 一、功能背景与技术选型 在团队协作场景中&#xff0c;群文件共享是核心需求之一。本文将介绍如何基于腾讯云IMCOS&#xff0c;在uniapp中实现&#xff1a; 群内文件上传/下载文件元数据管理下载进度追踪跨平台文件预览 二…...

[USACO23FEB] Bakery S

题目描述 Bessie 开了一家面包店! 在她的面包店里&#xff0c;Bessie 有一个烤箱&#xff0c;可以在 t C t_C tC​ 的时间内生产一块饼干或在 t M t_M tM​ 单位时间内生产一块松糕。 ( 1 ≤ t C , t M ≤ 10 9 ) (1 \le t_C,t_M \le 10^9) (1≤tC​,tM​≤109)。由于空间…...