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

相关文章

C语言中位操作的实际应用举例

《C语言中位操作的实际应用举例》:本文主要介绍C语言中位操作的实际应用,总结了位操作的使用场景,并指出了需要注意的问题,如可读性、平台依赖性和溢出风险,文中通过代码介绍的非常详细,需要的朋友可以参... 目录1. 嵌入式系统与硬件寄存器操作2. 网络协议解析3. 图像处理与颜色编码4. 高效处理布尔标志集合

Spring Boot 整合 SSE的高级实践(Server-Sent Events)

《SpringBoot整合SSE的高级实践(Server-SentEvents)》SSE(Server-SentEvents)是一种基于HTTP协议的单向通信机制,允许服务器向浏览器持续发送实... 目录1、简述2、Spring Boot 中的SSE实现2.1 添加依赖2.2 实现后端接口2.3 配置超时时

Python使用getopt处理命令行参数示例解析(最佳实践)

《Python使用getopt处理命令行参数示例解析(最佳实践)》getopt模块是Python标准库中一个简单但强大的命令行参数处理工具,它特别适合那些需要快速实现基本命令行参数解析的场景,或者需要... 目录为什么需要处理命令行参数?getopt模块基础实际应用示例与其他参数处理方式的比较常见问http

Python如何精准判断某个进程是否在运行

《Python如何精准判断某个进程是否在运行》这篇文章主要为大家详细介绍了Python如何精准判断某个进程是否在运行,本文为大家整理了3种方法并进行了对比,有需要的小伙伴可以跟随小编一起学习一下... 目录一、为什么需要判断进程是否存在二、方法1:用psutil库(推荐)三、方法2:用os.system调用

C++如何通过Qt反射机制实现数据类序列化

《C++如何通过Qt反射机制实现数据类序列化》在C++工程中经常需要使用数据类,并对数据类进行存储、打印、调试等操作,所以本文就来聊聊C++如何通过Qt反射机制实现数据类序列化吧... 目录设计预期设计思路代码实现使用方法在 C++ 工程中经常需要使用数据类,并对数据类进行存储、打印、调试等操作。由于数据类

Java中的Lambda表达式及其应用小结

《Java中的Lambda表达式及其应用小结》Java中的Lambda表达式是一项极具创新性的特性,它使得Java代码更加简洁和高效,尤其是在集合操作和并行处理方面,:本文主要介绍Java中的La... 目录前言1. 什么是Lambda表达式?2. Lambda表达式的基本语法例子1:最简单的Lambda表

Python实现特殊字符判断并去掉非字母和数字的特殊字符

《Python实现特殊字符判断并去掉非字母和数字的特殊字符》在Python中,可以通过多种方法来判断字符串中是否包含非字母、数字的特殊字符,并将这些特殊字符去掉,本文为大家整理了一些常用的,希望对大家... 目录1. 使用正则表达式判断字符串中是否包含特殊字符去掉字符串中的特殊字符2. 使用 str.isa

Linux下如何使用C++获取硬件信息

《Linux下如何使用C++获取硬件信息》这篇文章主要为大家详细介绍了如何使用C++实现获取CPU,主板,磁盘,BIOS信息等硬件信息,文中的示例代码讲解详细,感兴趣的小伙伴可以了解下... 目录方法获取CPU信息:读取"/proc/cpuinfo"文件获取磁盘信息:读取"/proc/diskstats"文

Python结合PyWebView库打造跨平台桌面应用

《Python结合PyWebView库打造跨平台桌面应用》随着Web技术的发展,将HTML/CSS/JavaScript与Python结合构建桌面应用成为可能,本文将系统讲解如何使用PyWebView... 目录一、技术原理与优势分析1.1 架构原理1.2 核心优势二、开发环境搭建2.1 安装依赖2.2 验

Java字符串操作技巧之语法、示例与应用场景分析

《Java字符串操作技巧之语法、示例与应用场景分析》在Java算法题和日常开发中,字符串处理是必备的核心技能,本文全面梳理Java中字符串的常用操作语法,结合代码示例、应用场景和避坑指南,可快速掌握字... 目录引言1. 基础操作1.1 创建字符串1.2 获取长度1.3 访问字符2. 字符串处理2.1 子字