c++全套流水账——染色法判断二分图,DFS的实践与应用

2023-11-05 17:30

本文主要是介绍c++全套流水账——染色法判断二分图,DFS的实践与应用,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

最近刷题比较多所以分享比较短也很少有视频了大家谅解一下。

染色法判断二分图

关于acwing

什么是二分图

二分图就是只你可以把一个图的点拉到左右两边。
这样它们就会变成两个集合。
那我们把原来图的边保留进这两个集合中。
最后如果我们可以使得这两个集合内部没有任何边,所有边都是两边互相连通的,我们称这个图为二分图。
否则不是二分图。
具体图片:
批注 2020-06-21 183219.png
这个图是二分图吗?
是的。
批注 2020-06-21 183313.png
批注 2020-06-21 183407.png
那这个呢?
不是。
批注 2020-06-21 183501.png
好了我们一会就证明为啥第二个一定不是。

二分图的特性

其实很简单,不能有奇数环。
啥是奇数环?
就是环上的点的数量是奇数。
很简单吧。
那我们是如何证明的呢?
请看下图。
我们把一个奇数环染色。
如果我们的这个是二分图:
那我们由一条边相连的两个点的数应该是不同的。
所以我们用01标完后我们就可以把标0的点放在1号集合。
标1的点放在2号集合。
这就很弱了对吧,我们给一个奇数环标一下就知道了。
批注 2020-06-21 185248.png

染色法判断二分图

依据上面这个原理,我们诞生了染色法。
我们可以把所有点染色撑出0,1。
那怎么染色呢?
没错就是dfs。
dfs搜索可以用来染色。
每次我们判断一下就好了。
判断一下如果我们的两个相邻的点染色相同,则这个图不是二分图。
那这个就很简单了。
我们来看一下具体模板题。
[模板]染色法判定二分图
本题题目:

给定一个n个点m条边的无向图,图中可能存在重边和自环。请你判断这个图是否是二分图。输入格式
第一行包含两个整数n和m。接下来m行,每行包含两个整数u和v,表示点u和点v之间存在一条边。输出格式
如果给定图是二分图,则输出“Yes”,否则输出“No”。数据范围
1≤n,m≤1e5
输入样例:
4 4
1 3
1 4
2 3
2 4
输出样例:
Yes

首先我们看一下数据范围。
数据范围是100000,我们再+一个10。

const int N = 100010;

或者:

const int N = 1e5 + 10;

接下来是读入。
这个就很简单了。
我们只要调用add函数存一个邻接表就行了。
注意是邻接表不是邻接矩阵!!!
一:

const int N = 100010;
int n, m, h[N], e[N], ne[N], idx, color[N];
void add(int a, int b)
{e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

二:

cin >> n >> m;
memset(h, -1, sizeof h);
for(int i = 0; i < m; i ++)
{int a,b;cin >> a >> b;add(a, b);
}

memset那行很重要!如果一不小心忘写了……
就挖了……
批注 2020-06-21 204046.png
有一次就因为这玩意找了半个小时的bug,最后自闭了/误
然后我们来看看中间这个部分。
我们的的dfs有这么几个参数:

  1. u,表示需要染色的点
  2. c,表示染的颜色

所以:

bool dfs(int u, int c)

然后我们来想一下怎么判断。
我们遍历一遍所有点然后看一下染色结果就行了。
这个也没啥好讲的。

bool f = true;
for(int i = 1; i <= n; i ++)
{if(!color[i]){if(!dfs(i, 0)) {f = false;break;}}
}

接着我们来说一下dfs部分怎么写。
首先标记这个点。

color[u] = c;

接下来我们遍历一下。

for(int i = h[u]; i != -1; i = ne[i])

用j表示这个点。

int j = e[i];

接下来看一下这个点有没有染过色,如果没染过就继续往深里执行。
这不就是DFS吗?我好能水

if(!color[j])
{if(!dfs(j, 3 - c)) return false;
}

否则我们判断一下两个点染的色是否一样。
一样就返回false。

else if(color[j] == c) return false;

这里的color就是这个被遍历到的点染的色。
c就是这个点染的色。
所以判断这俩东西是否相等就行了。
最后如果这波都挺下来了就返回true。
dfs部分完整代码:

bool dfs(int u, int 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 false;}else if(color[j] == c) return false;}return true;
}

输出我就不水了,大家看完整代码吧。

#include<bits/stdc++.h>using namespace std;const int N = 100010;int n, m;
int h[N], e[N], ne[N], idx;
int color[N];void add(int a, int b)
{e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}bool dfs(int u, int 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 false;}else if(color[j] == c) return false;}return true;
}int main()
{cin >> n >> m;for(int i = 0; i < m; i ++){int a,b;cin >> a >> b;add(a, b);}bool f = true;for(int i = 1; i <= n; i ++){if(!color[i]){if(!dfs(i, 0)) {f = false;break;}}}if(f) cout << "Yes";else cout << "No";return 0;
}

好了这期分享就到这里了。

这里是我的全部分享

抱歉最近准备蓝桥杯青少组的比赛更新的比较慢(未来也会是这样)

大家谅解一下。

这期分享出的比较仓促也没有视频,非常抱歉。

这是作业,感谢@冷月无声re,差点忘了。

下期见!

(凑个整,250(wtcl))

这篇关于c++全套流水账——染色法判断二分图,DFS的实践与应用的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

Spring Boot 配置文件之类型、加载顺序与最佳实践记录

《SpringBoot配置文件之类型、加载顺序与最佳实践记录》SpringBoot的配置文件是灵活且强大的工具,通过合理的配置管理,可以让应用开发和部署更加高效,无论是简单的属性配置,还是复杂... 目录Spring Boot 配置文件详解一、Spring Boot 配置文件类型1.1 applicatio

Python中随机休眠技术原理与应用详解

《Python中随机休眠技术原理与应用详解》在编程中,让程序暂停执行特定时间是常见需求,当需要引入不确定性时,随机休眠就成为关键技巧,下面我们就来看看Python中随机休眠技术的具体实现与应用吧... 目录引言一、实现原理与基础方法1.1 核心函数解析1.2 基础实现模板1.3 整数版实现二、典型应用场景2

tomcat多实例部署的项目实践

《tomcat多实例部署的项目实践》Tomcat多实例是指在一台设备上运行多个Tomcat服务,这些Tomcat相互独立,本文主要介绍了tomcat多实例部署的项目实践,具有一定的参考价值,感兴趣的可... 目录1.创建项目目录,测试文China编程件2js.创建实例的安装目录3.准备实例的配置文件4.编辑实例的

Python 中的异步与同步深度解析(实践记录)

《Python中的异步与同步深度解析(实践记录)》在Python编程世界里,异步和同步的概念是理解程序执行流程和性能优化的关键,这篇文章将带你深入了解它们的差异,以及阻塞和非阻塞的特性,同时通过实际... 目录python中的异步与同步:深度解析与实践异步与同步的定义异步同步阻塞与非阻塞的概念阻塞非阻塞同步

Python Dash框架在数据可视化仪表板中的应用与实践记录

《PythonDash框架在数据可视化仪表板中的应用与实践记录》Python的PlotlyDash库提供了一种简便且强大的方式来构建和展示互动式数据仪表板,本篇文章将深入探讨如何使用Dash设计一... 目录python Dash框架在数据可视化仪表板中的应用与实践1. 什么是Plotly Dash?1.1

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

Android Kotlin 高阶函数详解及其在协程中的应用小结

《AndroidKotlin高阶函数详解及其在协程中的应用小结》高阶函数是Kotlin中的一个重要特性,它能够将函数作为一等公民(First-ClassCitizen),使得代码更加简洁、灵活和可... 目录1. 引言2. 什么是高阶函数?3. 高阶函数的基础用法3.1 传递函数作为参数3.2 Lambda

springboot集成Deepseek4j的项目实践

《springboot集成Deepseek4j的项目实践》本文主要介绍了springboot集成Deepseek4j的项目实践,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价... 目录Deepseek4j快速开始Maven 依js赖基础配置基础使用示例1. 流式返回示例2. 进阶

Java中&和&&以及|和||的区别、应用场景和代码示例

《Java中&和&&以及|和||的区别、应用场景和代码示例》:本文主要介绍Java中的逻辑运算符&、&&、|和||的区别,包括它们在布尔和整数类型上的应用,文中通过代码介绍的非常详细,需要的朋友可... 目录前言1. & 和 &&代码示例2. | 和 ||代码示例3. 为什么要使用 & 和 | 而不是总是使

C++中::SHCreateDirectoryEx函数使用方法

《C++中::SHCreateDirectoryEx函数使用方法》::SHCreateDirectoryEx用于创建多级目录,类似于mkdir-p命令,本文主要介绍了C++中::SHCreateDir... 目录1. 函数原型与依赖项2. 基本使用示例示例 1:创建单层目录示例 2:创建多级目录3. 关键注