【第二十四课】二分图: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;
}

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


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

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

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/390159.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

黄金交易策略(Nerve Nnife.mql4):移动止盈的设计

完整EA&#xff1a;Nerve Knife.ex4黄金交易策略_黄金趋势ea-CSDN博客 相较mt4的止盈止损&#xff0c;在ea上实现移动止盈&#xff0c;可以尽最大可能去获得更高收益。移动止盈的大体逻辑是&#xff1a;到达止盈点就开始追踪止盈&#xff0c;直到在最高盈利点回撤指定点数即平…

小程序或者浏览器chrome访问的时候出现307 interval redicrect内部http自动跳转到https产生的原理分析及解决方案

#小李子9479# 出现的情况如下&#xff0c;即我们访问http的时候&#xff0c;它会自动307重定向到https,产生的原因是&#xff0c; 当你通过https访问过一个没有配置证书的http的网站之后&#xff0c;你再访问http的时候&#xff0c;它就会自动跳转到https&#xff0c;导致访问…

【网站项目】228高校教师电子名片系统

&#x1f64a;作者简介&#xff1a;拥有多年开发工作经验&#xff0c;分享技术代码帮助学生学习&#xff0c;独立完成自己的项目或者毕业设计。 代码可以私聊博主获取。&#x1f339;赠送计算机毕业设计600个选题excel文件&#xff0c;帮助大学选题。赠送开题报告模板&#xff…

抽象的问题1

vue3&#xff0c;在使用v-mode绑定属性时&#xff0c;发生了奇怪的问题&#xff0c;渲染失败了 代码如下 <template><div><form><div>账号<input v-model"form_user_Data.username" type"text"></div><div>密…

【C语言相关问题】C语言中关于大小写字母转换的问题

大家好&#xff0c;这里是争做图书馆扫地僧的小白。非常感谢各位的支持&#xff0c;也期待着您的关注。 目前博主有着C语言、C、linux以及数据结构的专栏&#xff0c;内容正在逐步的更新。 希望对各位朋友有所帮助同时也期望可以得到各位的支持&#xff0c;有任何问题欢迎私信与…

OpenCV 笔记(22):图像的缩放——最近邻插值、双线性插值算法

1. 图像缩放 1.1 简介 图像缩放是指通过增加或减少像素来改变图像尺寸的过程&#xff0c;是图像处理中常见的操作。图像缩放会涉及效率和图像质量之间的权衡。 图像放大&#xff08;也称为上采样或插值&#xff09;的主要目的是放大原图像&#xff0c;以便在更高分辨率的显示设…

JavaWeb

一、技术栈 【1】 前端部分 HTML CSS JavaScript ES6 Nodejs npm vite vue3 router pinia axios element-plus … 【2】 后端部分 HTTP xml Tomcat Servlet Request Response Cookie Sesssion Filter Listener MySQL JDBC Druid Jackson lombok jwt … 二、JAVAWEB交互模…

QtApplets-线程池

QtApplets-线程池 ​ 今天咱们稍微看下Qt的线程池。QThreadPool&#xff0c;浅浅搞一下。 文章目录 QtApplets-线程池QThreadPoolQThreadPool 与 QThread 区别替代方案Qt Concurrent QThreadPool 与 Qt Concurrent 区别Demo运行效果 ☞ 源码 关键字&#xff1a; Qt、QRunnable…

爬虫之牛刀小试(十):爬取某宝手机商品的销量,价格和店铺

首先淘宝需要登录&#xff0c;这一点如果用selenium如何解决&#xff0c;只能手动登录&#xff1f;如果不用selenium&#xff0c;用cookies登录也可。但是验证码又是一个问题&#xff0c;现在的验证码五花八门&#xff0c;难以处理。 我们回到正题&#xff0c;假设你已经登录上…

【图论经典题目讲解】CF786B - Legacy 一道线段树优化建图的经典题目

C F 786 B − L e g a c y \mathrm{CF786B - Legacy} CF786B−Legacy D e s c r i p t i o n \mathrm{Description} Description 给定 1 1 1 张 n n n 个点的有向图&#xff0c;初始没有边&#xff0c;接下来有 q q q 次操作&#xff0c;形式如下&#xff1a; 1 u v w 表示…

P1219 八皇后 (dfs 表格坐标关系)

一个正常的dfs&#xff08;数据范围1-13&#xff09;&#xff0c;发现一条对角线上&#xff0c;分别符合和与差相等。因为有负数&#xff0c;这里我最开始开的是map&#xff0c;发现卡了最后一个点TLE&#xff0c;记录一下时间复杂度&#xff08; map&#xff0c;set的时间复杂…

算法--数论二

这里写目录标题 高斯消元高斯消元求线性方程组用途高斯消元的数学思想例题代码 二级目录 一级目录二级目录二级目录二级目录 一级目录二级目录二级目录二级目录 一级目录二级目录二级目录二级目录 一级目录二级目录二级目录二级目录 高斯消元 高斯消元求线性方程组 用途 这个…

《Linux 简易速速上手小册》第1章: Linux 系统基础(2024 最新版)

文章目录 1.1 Linux 操作系统概述1.1.1 重点基础知识1.1.2 重点案例&#xff1a;配置 Apache Web 服务器1.1.3 拓展案例 1&#xff1a;配置 SSH 服务以进行远程管理1.1.4 拓展案例 2&#xff1a;使用 Cron 定时任务 1.2 选择合适的 Linux 发行版1.2.1 重点基础知识1.2.2 重点案…

淘宝项目实战相关知识点

淘宝各个方面的布局大部分都是常规操作&#xff0c;在这里我就简单记录一下练习过程中的相关知识点&#xff0c;比较简短。相关知识点如下&#xff1a; 行高的取值 假设font-size为16px line-height:normal; line-height:1.5;24px&#xff0c;先继承后计算 line-height:200%;3…

win7自带截图工具保存失效解决办法

今日发现一台远航技术的win7中自带的截图工具使用时正常&#xff0c;保存图片时没有弹出保存位置的对话窗口&#xff0c;无法正常保存图片。解决方案如下&#xff1a; 1、进入注册表编辑器。开始-搜索程序和文件-输入 regedit 按下回车键&#xff0c;打开注册表&#xff1b; 2、…

MySQL篇----第十三篇

系列文章目录 文章目录 系列文章目录前言一、MySQL 支持事务吗?二、MySQL 里记录货币用什么字段类型好三、MySQL 有关权限的表都有哪几个?四、列的字符串类型可以是什么?前言 前些天发现了一个巨牛的人工智能学习网站,通俗易懂,风趣幽默,忍不住分享一下给大家。点击跳转…

C语言指针

小伙伴们应该都知道在C语言中指针是非常难学的&#xff0c;指针它经常与内存联系&#xff0c;指向存放数据的地址&#xff0c;这样据很容易使小伙伴们绕晕&#xff0c;下面我就来简单解析一下指针&#xff01; 一、内存和地址 像我们学生一样&#xff0c;每个学生都拥有自己的…

C语言希尔排序详解!!!速过

目录 希尔排序是什么&#xff1f; 关于时间复杂度 希尔排序的源代码 希尔排序源代码的详解 希尔排序是什么&#xff1f; 之前我们说了三个排序&#xff08;插入排序&#xff0c;选择排序&#xff0c;冒泡排序&#xff09;有需要的铁铁可以去看看之前的讲解。 但因为之前的…

老和尚背女人过河,小和尚不理解,返程路上睡大觉——早读

回程路上&#xff01; 引言代码第一篇 人民日报 夜读 新的一年成为最好的自己&#xff0c;遇见更好的生活第二篇(跳) 人民日报 来了 新闻早班车要闻社会政策 结尾 引言 今天应该算是回归正常的节奏了 这个点在高铁上爬了一下 没想到新闻早班车的排名终于回归正常 也就意味着大家…

SSM整合进阶操作

SSM整合&#xff1a; http://t.csdnimg.cn/0lgfl 响应格式统一 我们要保证一个项目中所有接口返回的数据格式的统一。这样无论是前端还是移动端开发获取到我们的数据后都能更方便的进行统一处理。 所以我们定义以下结果封装类 /*** 在将Java对象转换为JSON格式时&#xff0c;…