二分图判定和二分图最大匹配

1.二分图的定义

二分图是一种特殊的无向图，它的节点可以被划分为两个互不相交的集合，使得同一集合中的任意两个节点之间没有边相连，而不同集合中的节点之间都有边相连。

换句话说，如果一个无向图可以被划分为两个集合，并且所有边的两个端点都分别属于不同的集合，那么这个无向图就是一个二分图。

如图，有蓝色，绿色两个集合，集合内的点可以跟另一个集合内的点相互连接，但集合内部不能连接，这就叫二分图。

那么如何判定是否为二分图呢？这就要用到二分图的染色

2.二分图的染色

假设图中的颜色都还没标上，只有点和边，那么我们需要对各个点能直达的点染色（也就是不同集合的点的染不同颜色），如果能符合“相邻点的颜色不同”这个条件，就是一个二分图。

反之如下，两个蓝色的点之间有连线，可是他们颜色相同，就不能满足条件了

例题1

1.用vector建图，此时我们已经知道了各个点（记作点i）的所有邻接点（也就是只用走一条边就能到达的点），那么点i的邻接点j的颜色不能跟点i一样

2.如果点i是蓝色，点j就应该被染成绿色

3.我们要将以点i为起点，所有能到达的点都遍历，可以用dfs或者bfs

4.如果染的过程中，某点还没有染色，就将其染成相反色；

   如果已经染了色，且颜色为相反色，则不用管；

   如果已经染了色，且颜色相同，说明不满足条件，这不是一个二分图。

dfs写法

#include<cstdio>
#include<set>
#include<list>
#include<queue>
#include<math.h>
#include<stdlib.h>
#include<string>
#include<string.h>
#include <stdio.h>
#include<algorithm>
#include<iomanip>
#include<cmath>
#include<sstream>
#include<stack>
#include <utility>
#include<map>
#include <vector>

#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define inf 0x3f3f3f3f
//2147483647

#define int long long
//#include <bits/stdc++.h>
typedef long long ll;
#include<iostream>
using namespace std;

const int N = 1e6 + 10;
//long long MAX(long long a, long long b) { return a < b ? b : a; }



vector<int> edge[N];
int vis[N];//0为蓝色，1为绿色
bool ans = true;

void dfs(int cur, int c) {
	//作用：遍历cur能到达的点，并且将这些点染色
	vis[cur] = c;

	for (auto x : edge[cur]) {
		//遍历cur的邻接点
		if (vis[x] == -1) {
			//还未被染色
			dfs(x, 1 - c);
			//将x点染成跟cur不一样的颜色
			//并且开始深搜
		}
		else if (vis[x] == vis[cur]) {
			ans = false;
		}
	}

}
signed main() {
	memset(vis, -1, sizeof vis);
	int n, m; cin >> n >> m;
	while (m--) {
		int a, b; cin >> a >> b;
		edge[a].push_back(b);
		edge[b].push_back(a);

	}
	for (int i = 1; i <= n; i++) {
		if (vis[i] == -1) dfs(i, 1);
	}

	if (ans) cout << "Yes";
	else cout << "No";
	return 0;
}

bfs写法

#include<assert.h>
#include<cstdio>
#include<set>
#include<list>
#include<queue>
#include<math.h>
#include<stdlib.h>
#include<string>
#include<string.h>
#include <stdio.h>
#include<algorithm>
#include<iomanip>
#include<cmath>
#include<sstream>
#include<stack>
#include <utility>
#include<map>
#include <vector>

#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define inf 0x3f3f3f3f
//2147483647

#define int long long
//#include <bits/stdc++.h>
typedef long long ll;
#include<iostream>
using namespace std;

const int N = 1e6 + 10;
//long long MAX(long long a, long long b) { return a < b ? b : a; }



vector<int> edge[N];
int vis[N];//0为蓝色，1为绿色
bool ans = true;

void bfs(int cur) {
	//作用：遍历cur能到达的点，并且将这些点染色
	

	queue<int> q;
	q.push(cur);
	vis[cur] = 0;
	while (!q.empty()) {
		int t = q.front();
		
		q.pop();
		for (auto x : edge[t]) {
			if (vis[x] == -1) {
				q.push(x);
				vis[x] = 1 - vis[t];
			}
			else if (vis[x] == vis[t]) {
				ans = false;
				return;
			}
		}

	}

}
signed main() {
	memset(vis, -1, sizeof vis);
	int n, m; cin >> n >> m;
	while (m--) {
		int a, b; cin >> a >> b;
		edge[a].push_back(b);
		edge[b].push_back(a);

	}
	for (int i = 1; i <= n; i++) {
		if (vis[i] == -1) bfs(i);
	}

	if (ans) cout << "Yes";
	else cout << "No";
	return 0;
}

例题2

D - Good Tuple Problem

分析：atcoder周赛，基本就是模板题了

#include<cstdio>
#include<set>
#include<list>
#include<queue>
#include<math.h>
#include<stdlib.h>
#include<string>
#include<string.h>
#include <stdio.h>
#include<algorithm>
#include<iomanip>
#include<cmath>
#include<sstream>
#include<stack>
#include <utility>
#include<map>
#include <vector>

#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define inf 0x3f3f3f3f
//2147483647

#define int long long
//#include <bits/stdc++.h>
typedef long long ll;
#include<iostream>
using namespace std;

const int N = 1e6 + 10;
//long long MAX(long long a, long long b) { return a < b ? b : a; }



vector<int> dif[N];//dif[i]存的是，需要跟i结点不同的结点
int a[N], b[N], x[N];
bool ans = true;

void dfs(int i, int s) {
	x[i] = s;
	for (int j = 0; j < dif[i].size(); j++) {
		if (x[dif[i][j]] == -1) {
			dfs(dif[i][j], 1 - s);
		}
		else if (x[dif[i][j]] == x[i]) ans = false;
	}

}
signed main() {
	int n, m; cin >> n >> m;

	for (int i = 0; i < m; i++) {
		cin >> a[i];
	}
	for (int i = 0; i < m; i++) {
		cin >> b[i];
	}
	for (int i = 0; i < m; i++) {
		dif[a[i]].push_back(b[i]);
		dif[b[i]].push_back(a[i]);
	}

	memset(x, -1, sizeof x);
	for (int i = 1; i <= n; i++) {
		if(x[i]==-1) dfs(i, 0);
	}

	if (ans) cout << "Yes";
	else cout << "No";

	return 0;
}

3.匈牙利算法

匈牙利算法是用来求二分图的最大匹配数，注意！是最大匹配数，是无权的

假设有这些男生和女生，男生对一些女生中意，问怎么匹配才能让匹配出来的情侣数量最多

答：我们把下面的行为看成一个“追”的动作

男生i一个个访问自己中意的女生，如果该女生j还没有对象，则直接匹配成功。

如果女生j有对象，即match[j]这个男生，那么去找找看match[j]这个男生能不能换一个女朋友（即女生j有调整空间），然后把女生j让给男生i。如果可以，则男生i也匹配成功。

如果男生i遍历完所有中意的女生还是找不到，就匹配失败。

着重解释一下st[]。作用是不重复访问同一个女生，导致递归陷入死循环。

我们可以把st[]的作用看成一个“预定”的行为，当女生j还没被预定，则使其被预定，即st[j] = true，看看这个女朋友能不能追到手（也就是我上面“答”的部分）。不行的话去看看其他中意的女生。

注意！不论女生j追没追到手，她都已经是被”预定“过了，后续不能再访问。

那到底是怎么陷入死循环的呢？

如果没有st数组的情况如下。

当男生i访问到了女生j，女生j已经有男生k当男朋友了，那么此时就要看看男生k能不能换别的女朋友。所以男生k就会遍历所有自己中意的女生，看看有没有未被选的女生，或者有调整空间的女生。

问题就出在这里！这样的话男生k可能又会访问到女生j，然后看女生j有没有调整空间，也就是自己有没有调整空间，陷入递归死循环！

因此，st[]的存在是必要的。

#include<cstdio>
#include<set>
#include<list>
#include<queue>
#include<math.h>
#include<stdlib.h>
#include<string>
#include<string.h>
#include <stdio.h>
#include<algorithm>
#include<iomanip>
#include<cmath>
#include<sstream>
#include<stack>
#include <utility>
#include<map>
#include <vector>

#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define inf 0x3f3f3f3f
//2147483647

#define int long long
//#include <bits/stdc++.h>
typedef long long ll;
#include<iostream>
using namespace std;

const int N = 1e6 + 10;
//long long MAX(long long a, long long b) { return a < b ? b : a; }

int cnt = 0;
int head[N], e[N], ne[N];
int match[N];
bool st[N];

void add(int u, int v) {
	e[cnt] = v, ne[cnt] = head[u], head[u] = cnt++;
}

bool find(int x) {
	//找x能不能配对到女朋友
	
	//遍历x所中意的女生
	for (int i = head[x]; i != -1; i = ne[i]) {
		int j = e[i];
		if (!st[j]) {
			st[j] = true;
			if (match[j]==0 || find(match[j])) {
				//如果女生j没有男朋友，或者女生当前的男朋友可以选择其他女生
				//那么就让那个男生去找别的女生，男生x跟女生j匹配
				match[j] = x;
				return true;
			}

		}

	}
	return false;
}

int a, b, n;
signed main() {
	memset(head, -1, sizeof head);
	cin >> a >> b >> n;
	for (int i = 0; i < n; i++) {
		int u, v, w; cin >> u >> v;
		add(u, v);
	}

	int ans = 0;
	for (int i = 1; i <= a; i++) {
		memset(st, false, sizeof st);
		if (find(i)) ans++;

	}
	cout << ans;

	return 0;
}

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

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

相关文章

Keil文本对齐

Keil文本对齐

摘要&#xff1a;通常我们写代码的时候&#xff0c;尤其是缩进和{}的使用&#xff0c;很多都需要自己手动去调整&#xff0c;如果有一个自动格式化代码的工具&#xff0c;每次编辑完代码&#xff0c;然后一键给将代码格式化&#xff0c;即省时又美观。为了解决这个问题&#xf…
阅读更多...
面向对象高级

面向对象高级

本期对应知识库&#xff1a;&#xff08;持续更新中&#xff01;&#xff09; 面向对象高级 (yuque.com) ​​​​​​​尚硅谷_宋红康_对象内存解析.pptx static 适用于公用变量 开发中&#xff0c;变量 经常把一些常量设置为静态static 例如 PI 方法 经常把工具类中的方…
阅读更多...
Deepsort项目详解

Deepsort项目详解

一、目标追踪整体代码 代码目录如下图所示&#xff1a; 、 追踪相关代码&#xff1a; 检测相关代码和权重 调用 检测 和 追踪的代码&#xff1a; 首先代码分为三个部分&#xff1a; 目标追踪的相关代码和权重目标检测相关代码和权重&#xff0c;这里用的是yolov5.5目标检…
阅读更多...
Thinkphp8 - 连接多个数据库

Thinkphp8 - 连接多个数据库

// 数据库连接配置信息connections > [mysql > [// 数据库类型type > mysql,// 服务器地址hostname > 127.0.0.1,// 数据库名database > thinkphp,// 用户名username > env(DB_USER, root),// 密码password >…
阅读更多...
layui 表格（table）合计 取整数

layui 表格（table）合计 取整数

第一步 开启合计行 是否开启合计行区域 table.render({elem: #myTable, url: ../baidui/, page: true, cellMinWidth: 100,totalRow:true,cols: [[ //表头//{ type: checkbox },{ type: checkbox,totalRowText: "合计" },//合计行区域{ field: id, align: center,…
阅读更多...
【0基础学Java第九课】-- 抽象类和接口

【0基础学Java第九课】-- 抽象类和接口

9. 抽象类和接口 9.1 抽象类9.1.1 抽象类概念9.1.2 抽象类语法9.1.3 抽象类的特性9.1.4 抽象类的作用 9.2 接口9.2.1 接口的概念9.2.2 语法规则9.2.3 接口使用9.2.4 接口特性9.2.5 实现多个接口9.2.6 接口的继承9.2.9 抽象类和接口的区别 9.3 Object类9.3.1 获取对象方法9.3.1 …
阅读更多...
基于springboot实现驾校管理系统项目【项目源码】计算机毕业设计

基于springboot实现驾校管理系统项目【项目源码】计算机毕业设计

基于springboot实现驾校管理系统演示 JAVA简介 JavaScript是一种网络脚本语言&#xff0c;广泛运用于web应用开发&#xff0c;可以用来添加网页的格式动态效果&#xff0c;该语言不用进行预编译就直接运行&#xff0c;可以直接嵌入HTML语言中&#xff0c;写成js语言&#xff0…
阅读更多...
小H靶场学习笔记：DC-2

小H靶场学习笔记：DC-2

DC-2 Created: November 10, 2023 3:01 PM Tags: WordPress, git提权, rbash逃逸 Owner: 只会摸鱼 靶场过程 信息收集 扫描存活主机&#xff0c;找到靶机ip&#xff1a;192.168.199.131&#xff08;本机是192.168.199.129&#xff09; 扫描端口开放协议 发现有80端口和77…
阅读更多...
电路设计之36V 自动断电和防浪涌电路

电路设计之36V 自动断电和防浪涌电路

1. 电路图纸 2. 解释防浪涌功能怎么实现的 1. 首先当电源上电的一瞬间是 电容C1 是相当于短路的。 &#xff08;电容的充电状态。电容充电相当于短路状态&#xff09; 2. 当上电的一瞬间是有 浪涌的。 3.当上电的瞬间有浪涌的&#xff0c;此时电容C1 相当于短路&#xff0c;所…
阅读更多...
Java学习_对象

Java学习_对象

对象在计算机中的执行原理 类和对象的一些注意事项 this关键字 构造器 构造器是一种特殊的方法 : 特殊之处在于&#xff0c;名字必须与所在类的名字一样&#xff0c;而且不能写返回值类型 封装 封装的设计规范&#xff1a;合理隐藏、合理暴露 实体类 成员变量和局部变量的区别 …
阅读更多...
有源RS低通滤波

有源RS低通滤波

常用的滤波电路有无源滤波和有源滤波两大类。若滤波电路元件仅由无源元件&#xff08;电阻、电容、电感&#xff09;组成&#xff0c;则称为无源滤波电路。无源滤波的主要形式有电容滤波、电感滤波和复式滤波(包括倒L型、LC滤波、LCπ型滤波和RCπ型滤波等)。若滤波电路不仅有无…
阅读更多...
【Redis】list列表

【Redis】list列表

上一篇&#xff1a; String 类型 https://blog.csdn.net/m0_67930426/article/details/134362606?spm1001.2014.3001.5501 目录 Lpush LRange Rpush Lpop Rpop Lindex Ltrim Lset 列表不存在的情况 如果列表存在 Linsert ​编辑 在………之前插入 在……后面插入…
阅读更多...
UE地形系统材质混合实现和Shader生成分析(UE5 5.2)

UE地形系统材质混合实现和Shader生成分析(UE5 5.2)

前言 随着电脑和手机硬件性能越来越高&#xff0c;游戏越来越追求大世界&#xff0c;而大世界非常核心的一环是地形系统&#xff0c;地形系统两大构成因素&#xff1a;高度和多材质混合&#xff0c;此篇文章介绍下UE4/UE5 地形的材质混合方案----基于WeightMap混合。 材质层 …
阅读更多...
总结：利用JDK原生命令，制作可执行jar包与依赖jar包

总结：利用JDK原生命令，制作可执行jar包与依赖jar包

总结&#xff1a;利用JDK原生命令&#xff0c;制作可执行jar包与依赖jar包 一什么是jar包&#xff1f;二制作jar包的工具&#xff1a;JDK原生自带的jar命令&#xff08;1&#xff09;jar命令注意事项&#xff1a;&#xff08;2&#xff09;jar包清单文件创建示例&#xff1a;&a…
阅读更多...
Yolo自制detect训练

Yolo自制detect训练

Install 把代码拉下来 GitHub - ultralytics/yolov5 at v5.0 然后 pip install -r requirements.txt 安装完了，运行一下detect.py即可 结果会保存在对应的目录下 Intro ├── data：主要是存放一些超参数的配置文件（这些文件（yaml文件）是用来配置训练集和测试集还有验…
阅读更多...
【Redis】set 集合

【Redis】set 集合

上一篇&#xff1a;list 列表 https://blog.csdn.net/m0_67930426/article/details/134364315?spm1001.2014.3001.5501 目录 Sadd Smembers Sismember Scard Srem ​编辑Srandomember Spop Smove 集合类 Sdiff Sinter Sunion 官网 https://redis.io/commands/?…
阅读更多...
01-Spring中的工厂模式

01-Spring中的工厂模式

工厂模式 工厂模式的三种形态: 工厂模式是解决对象创建问题的属于创建型设计模式,Spring框架底层使用了大量的工厂模式 第一种&#xff1a;简单工厂模式是工厂方法模式的一种特殊实现,简单工厂模式又叫静态工厂方法模式不属于23种设计模式之一第二种&#xff1a;工厂方法模式…
阅读更多...
记录一次某某虚拟机的逆向

记录一次某某虚拟机的逆向

导语 学了一段时间的XPosed&#xff0c;发现XPosed真的好强&#xff0c;只要技术强&#xff0c;什么操作都能实现... 这次主要记录一下我对这款应用的逆向思路 apk检查 使用MT管理器检查apk的加壳情况 发现是某数字的免费版本 直接使用frida-dexdump 脱下来后备用 应用分…
阅读更多...
基于springboot实现桥牌计分管理系统项目【项目源码】

基于springboot实现桥牌计分管理系统项目【项目源码】

基于springboot实现桥牌计分管理系统演示 JAVA简介 JavaScript是一种网络脚本语言&#xff0c;广泛运用于web应用开发&#xff0c;可以用来添加网页的格式动态效果&#xff0c;该语言不用进行预编译就直接运行&#xff0c;可以直接嵌入HTML语言中&#xff0c;写成js语言&#…
阅读更多...
Lambertian模型（完美漫反射）

Lambertian模型（完美漫反射）

这里使用相乘的方式组合光照色和纹理色。根据这个模型,面朝光源的区域光照强度高,纹理色也相应增强。面背光源的区域光照弱,纹理色也被抑制。这样通过光照和纹理的结合,可以合成出具有照明效果的面部颜色,而不仅仅是固定的纹理本身的颜色。相乘方式可以近似实现不同光照方向下面…
阅读更多...
最新文章

Copyright @ 2022~2023