【第二十四课】二分图:acwing-860染色法判定二分图 / acwing-861二分图的最大匹配 ( c++代码 )

本文主要是介绍【第二十四课】二分图:acwing-860染色法判定二分图 / acwing-861二分图的最大匹配 ( c++代码 ),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

目录

二分图是什么 

acwing-860染色法判定二分图

染色法

代码

acwing-861二分图的最大匹配

思路

代码


 

二分图是什么 

学习二分图的目的就是一些题目可以简化成二分图的模型来求解。 

二分图也就是:一个无向图顶点集,分成了两堆顶点(可以理解为两种不同性质),图中的每条边的两个端点分别属于两个不同的顶点集合这两个顶点集内部顶点之间没有边,所有的边都是连接两个不同顶点集合内的顶点

一个图是二分图当且仅当它不包含奇环图。(这句话正反都成立。

奇环图就是存在:边数是奇数的环 的图。

正向解释:假设存在一个奇数长度的环,那么环上的节点一定是交替属于两个集合,由于环的长度是奇数,环的最后一个节点又必须与环的起始节点相连,且它们属于同一个集合,这与二分图的定义相矛盾。因此,如果图是二分图,则不可能存在奇数长度的环

反之:如果一个图不包含奇环,那么我们通过染色法(后面会说)遍历图中的每一个节点,相邻两个节点染色不同,如果最终没有发生染色冲突的情况(即相邻的节点被染成了相同的颜色),那么就证明该图是二分图。

acwing-860染色法判定二分图

染色法

上面简单提过,其实叫染色法也只是一种标记而已,不用想的太复杂。

我们遍历图中的每个节点,将其染色,由于一个点染色之后,与其相直连的其他顶点应该染什么色应该是固定的,对吧?因为二分图的定义嘛:如果这个点还没被染色,就染成与该点不同的颜色,如果已经被染过色,就判断所染的颜色是否与该点的颜色相同。 如果发现有冲突,就说明不是二分图,直接跳出循环。

我们这里采用深度优先遍历,递归地对节点及其相邻节点进行染色,并且检查相邻节点是否与当前节点的颜色相同

代码

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1e5+10,M=2e5+10;
int n,m;
int h[N],e[M],ne[M],idx;
int color[N];//用俩标记是否被染色
void add(int x,int y)
{e[idx]=y;ne[idx]=h[x];h[x]=idx++;
}
bool dfs(int u,int c)//c表示该点被染的颜色
{color[u]=c;for(int i=h[u];i!=-1;i=ne[i]){int j=e[i];if(!color[j]){if(!dfs(j,3-c))return 0;}else if(color[j]==c)return 0;}return 1;
}
int main()
{cin>>n>>m;memset(h,-1,sizeof h);while(m--){int u,v;cin>>u>>v;add(u,v);//无向图add(v,u);}bool flag=1;//作为标记for(int i=1;i<=n;i++)//遍历所有顶点{if(!color[i])//如果该点没有被染色{if(!dfs(i,1))//就通过dfs将其染色,并判断染色是否存在冲突{flag=0;break;}}}if(flag)puts("Yes");else puts("No");return 0;
}

3-c作为染色,是因为我们这里用1 2分别表示染成的两种不同的颜色,而3-c刚好能够得到与前一个点的c不同的颜色。

acwing-861二分图的最大匹配

思路

首先要搞清楚匹配的概念:

可以直白地理解为:最多能有几对 一对一 的边

为了尽可能的得到最大的匹配数,有增广路径的概念,嗯,,

我这里按照图中说一下:比如1号点最开始应该直接匹配的是4号点,但是在对3号点进行匹配的时候,我们发现3号点只能与1号点匹配,于是我们就想让1号点再找找有没有其他可以选择的(3号点只有1号,只好让1号点变一变啦),发现1号点还可以与6号点匹配,那这样就皆大欢喜啦,我们多了一个匹配数。如果1号点也只有4号点能匹配,那最大匹配数就只有2啦。

所以我们这里的思路就是,只看左侧顶点,寻找可以与其匹配的右侧顶点。注意每次开始针对一个左侧顶点寻找之前,先把右侧顶点的标记都初始化一下,避免与之前的标记混淆。

find函数的主要思路就是,遍历这个左侧顶点直连的右侧顶点,观察其是否已经被访问过。未被访问的情况下:我们尝试为其寻找匹配的左侧顶点。[注意这里的思路是:为右侧顶点寻找可以匹配的左侧顶点]

有两种可能的情况:①该右侧顶点未被匹配过  ②该右侧顶点已经在前面几轮被匹配过了,名花有主了

-

①如果右侧顶点 j 尚未匹配(即 match[j] == 0),那么我们直接将其匹配给当前左侧顶点 x,并返回 1。

-

②如果右侧顶点 j 已经匹配了一个左侧顶点 y(即 match[j] 不为 0),我们需要尝试找到另一个左侧顶点与右侧顶点 j 匹配(递归调用)

为了实现上述所说的处理冲突以得到更大的匹配数的目的,我们定义match数组,其下标表示右侧顶点,数组存储的是右侧顶点所对的左侧顶点,当遇到了所谓的“冲突”,我们就再找找该右侧顶点所对的左侧顶点是否还有其他的顶点可以匹配

代码

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=510,M=1e5+10;
int n1,n2,m;
int h[N],e[M],ne[M],idx;//由于我们只考虑左侧的点,因此采用邻接表存储是合理的
int match[N];//记录右侧顶点匹配的左侧顶点编号:下标表示右侧顶点 match数组表示的是左侧顶点
bool st[N];//标记右侧顶点是否已经被访问
void add(int u,int v)
{e[idx]=v;ne[idx]=h[u];h[u]=idx++;
}
bool find(int x)
{for(int i=h[x];i!=-1;i=ne[i]){int j=e[i];if(!st[j])//先检查右侧顶点 j 在这一轮中是否被访问过{st[j]=1;if(match[j]==0 || find(match[j])){match[j]=x;return 1;}}}return 0;
}
int main()
{cin>>n1>>n2>>m;memset(h,-1,sizeof h);while(m--){int u,v;cin>>u>>v;add(u,v);//因为只需要遍历左侧顶点}int res=0;for(int i=1;i<=n1;i++)//遍历左侧节点{memset(st,0,sizeof st);//以便重新标记每个右侧顶点的访问状态,不会受到之前搜索状态的影响if(find(i))res++;}cout<<res;return 0;
}

上面思路明白之后代码应该不难理解。 


写到这里。感觉时间好像有点紧😂。。嗯,,,

有问题欢迎指出,一起加油!!!

这篇关于【第二十四课】二分图:acwing-860染色法判定二分图 / acwing-861二分图的最大匹配 ( c++代码 )的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/715870

相关文章

springboot循环依赖问题案例代码及解决办法

《springboot循环依赖问题案例代码及解决办法》在SpringBoot中,如果两个或多个Bean之间存在循环依赖(即BeanA依赖BeanB,而BeanB又依赖BeanA),会导致Spring的... 目录1. 什么是循环依赖?2. 循环依赖的场景案例3. 解决循环依赖的常见方法方法 1:使用 @La

使用C#代码在PDF文档中添加、删除和替换图片

《使用C#代码在PDF文档中添加、删除和替换图片》在当今数字化文档处理场景中,动态操作PDF文档中的图像已成为企业级应用开发的核心需求之一,本文将介绍如何在.NET平台使用C#代码在PDF文档中添加、... 目录引言用C#添加图片到PDF文档用C#删除PDF文档中的图片用C#替换PDF文档中的图片引言在当

C#使用SQLite进行大数据量高效处理的代码示例

《C#使用SQLite进行大数据量高效处理的代码示例》在软件开发中,高效处理大数据量是一个常见且具有挑战性的任务,SQLite因其零配置、嵌入式、跨平台的特性,成为许多开发者的首选数据库,本文将深入探... 目录前言准备工作数据实体核心技术批量插入:从乌龟到猎豹的蜕变分页查询:加载百万数据异步处理:拒绝界面

用js控制视频播放进度基本示例代码

《用js控制视频播放进度基本示例代码》写前端的时候,很多的时候是需要支持要网页视频播放的功能,下面这篇文章主要给大家介绍了关于用js控制视频播放进度的相关资料,文中通过代码介绍的非常详细,需要的朋友可... 目录前言html部分:JavaScript部分:注意:总结前言在javascript中控制视频播放

Spring Boot 3.4.3 基于 Spring WebFlux 实现 SSE 功能(代码示例)

《SpringBoot3.4.3基于SpringWebFlux实现SSE功能(代码示例)》SpringBoot3.4.3结合SpringWebFlux实现SSE功能,为实时数据推送提供... 目录1. SSE 简介1.1 什么是 SSE?1.2 SSE 的优点1.3 适用场景2. Spring WebFlu

java之Objects.nonNull用法代码解读

《java之Objects.nonNull用法代码解读》:本文主要介绍java之Objects.nonNull用法代码,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐... 目录Java之Objects.nonwww.chinasem.cnNull用法代码Objects.nonN

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.

python+opencv处理颜色之将目标颜色转换实例代码

《python+opencv处理颜色之将目标颜色转换实例代码》OpenCV是一个的跨平台计算机视觉库,可以运行在Linux、Windows和MacOS操作系统上,:本文主要介绍python+ope... 目录下面是代码+ 效果 + 解释转HSV: 关于颜色总是要转HSV的掩膜再标注总结 目标:将红色的部分滤

在C#中调用Python代码的两种实现方式

《在C#中调用Python代码的两种实现方式》:本文主要介绍在C#中调用Python代码的两种实现方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录C#调用python代码的方式1. 使用 Python.NET2. 使用外部进程调用 Python 脚本总结C#调

C++ 中的 if-constexpr语法和作用

《C++中的if-constexpr语法和作用》if-constexpr语法是C++17引入的新语法特性,也被称为常量if表达式或静态if(staticif),:本文主要介绍C++中的if-c... 目录1 if-constexpr 语法1.1 基本语法1.2 扩展说明1.2.1 条件表达式1.2.2 fa