当前位置: 首页 > news >正文

acwing算法基础之搜索与图论--染色法判断二分图

目录

  • 1 基础知识
  • 2 模板
  • 3 工程化

1 基础知识

二分图:每条边连接的起点和终点,分别属于集合A和集合B。

一个图是二分图,当且仅当,图中不含奇数环(即,回环中的结点数目是奇数)。

染色法判定二分图的关键步骤为:

  1. 初始化颜色数组color[1~n] = 0。
  2. 遍历每一个结点a:如果它没有被染色,将其染色为1,即dfs(a, 1)。
  3. 如果没有矛盾,则说明该图是二分图,否则,不是。
bool dfs(int x, int c) {color[a] = c;//递归处理它的子结点for (auto b : g[a]) {if (!color[b]) {if (!dfs(b, 3 - c)) return false; } else {if (color[b] == c) return false;}}return true;
}

2 模板

int n;      // n表示点数
int h[N], e[M], ne[M], idx;     // 邻接表存储图
int color[N];       // 表示每个点的颜色,-1表示未染色,0表示白色,1表示黑色// 参数:u表示当前节点,c表示当前点的颜色
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] == -1){if (!dfs(j, !c)) return false;}else if (color[j] == c) return false;}return true;
}bool check()
{memset(color, -1, sizeof color);bool flag = true;for (int i = 1; i <= n; i ++ )if (color[i] == -1)if (!dfs(i, 0)){flag = false;break;}return flag;
}

3 工程化

题目1:请判断该图是否为二分图。

#include <iostream>
#include <cstring>
#include <vector>using namespace std;const int N = 1e5 + 10;
int n, m;
vector<vector<int>> g(N);
int color[N];bool dfs(int a, int c) {color[a] = c;//看结点a能走到哪儿for (auto b : g[a]) {if (!color[b] && !dfs(b, 3 - c)) return false;if (color[b] && color[b] == c) return false;}return true;
}int main() {cin >> n >> m;int a, b;while (m--) {cin >> a >> b;g[a].emplace_back(b);g[b].emplace_back(a);}bool flag = true;for (int i = 1; i <= n; ++i) {if (!color[i] && !dfs(i, 1)) {flag = false;break;}}if (flag) {cout << "Yes" << endl;} else {cout << "No" << endl;}return 0;
}

相关文章:

acwing算法基础之搜索与图论--染色法判断二分图

目录 1 基础知识2 模板3 工程化 1 基础知识 二分图&#xff1a;每条边连接的起点和终点&#xff0c;分别属于集合A和集合B。 一个图是二分图&#xff0c;当且仅当&#xff0c;图中不含奇数环&#xff08;即&#xff0c;回环中的结点数目是奇数&#xff09;。 染色法判定二分…...

塔式服务器是什么服务器?

在当今数字时代&#xff0c;数据的处理和存储需求不断增长&#xff0c;企业和组织需要强大而可靠的服务器来支持其业务运营和数据管理。塔式服务器作为一种常见的服务器架构&#xff0c;以其出色的性能、灵活性和可扩展性成为了许多企业和组织的首选。 塔式服务器的外观类似于…...

nodejs+express接口全局拦截和环境变量设置

前言&#xff1a; 本例中必须安装的依赖包有&#xff1a;express、cookie-parser(可以没有) 1. 接口全局拦截 新建一个文件intercept.ts&#xff0c;编写拦截过程 import express from "express"; import cookieParser from cookie-parserconst ssoRouter expre…...

深度学习之基于YoloV5的目标检测和双目测距系统

欢迎大家点赞、收藏、关注、评论啦 &#xff0c;由于篇幅有限&#xff0c;只展示了部分核心代码。 文章目录 一项目简介 二、功能三、系统四. 总结 一项目简介 双目测距系统利用两个相机的图像来计算目标到相机的距离。通过对左右相机图像进行立体匹配&#xff0c;可以获得目标…...

如何显示标注的纯黑mask图

文章目录 前言一、二分类mask显示二、多分类mask显示 前言 通常情况下&#xff0c;使用标注软件标注的标签图看起来都是纯黑的&#xff0c;因为mask图为单通道的灰度图&#xff0c;而灰度图一般要像素值大于128后&#xff0c;才会逐渐显白&#xff0c;255为白色。而标注的时候…...

【算法每日一练]-图论(保姆级教程 篇1(模板篇)) #floyed算法 #dijkstra算法 #spfa算法

今天开始讲图论 目录 图的存储 算任意两点的最短路径: floyed算法&#xff1a; 算一个点到其他所有点的最短距离 dijkstra算法: spfa算法&#xff1a; 图的存储 其实&#xff1a;邻接矩阵和链式向前星都能存边的信息&#xff0c;vector只能存点的信息&#xff0c;再搭配上v[]…...

c语言数据结构---十字链表

#include<stdio.h> #include<stdlib.h> typedef struct node{//十字链表 输入三元组返回矩阵 int row,col,val;struct node *down,*right; }JD,*J; typedef struct {J *rhead,*chead;int mu,nu,tu;//行列非0元 }CS; CS creat(CS M){int m,n,t;;int k,j,e;JD *p,*q…...

使用python电脑轻量级控制手机—adb命令和手机投屏

文章目录 一、通过无线连接手机和电脑二、使用adb命令轻量级控制手机二、使用scrcpy控制手机 通过电脑控制手机有多种方式如appnium等&#xff0c;本文介绍的是两种轻量级的方案&#xff0c;使用adb命令刚和手机投屏。 一、通过无线连接手机和电脑 1、手机设置 开发者选项—us…...

VBA技术资料MF82:替换文件夹中文件名中的字符

我给VBA的定义&#xff1a;VBA是个人小型自动化处理的有效工具。利用好了&#xff0c;可以大大提高自己的工作效率&#xff0c;而且可以提高数据的准确度。我的教程一共九套&#xff0c;分为初级、中级、高级三大部分。是对VBA的系统讲解&#xff0c;从简单的入门&#xff0c;到…...

如何利用大模型蒸馏出小模型实现降本

如何让小模型的推理效果在某些领域比 ChatGPT 这样的大模型还要更强&#xff1f;这篇论文提供了一个思路&#xff1a;https://arxiv.org/abs/2212.10071&#xff0c;借助思维链&#xff08;CoT&#xff09;逐步解决复杂推理任务的能力&#xff0c;可以使用大模型作为推理教师&a…...

CentOS 中启动 Jar 包

在 CentOS 中启动一个 Jar 包&#xff0c;可以通过 java 命令来实现。具体步骤如下&#xff1a; 确认 Java 环境已经安装并配置好了。 打开终端或者 SSH 连接到 CentOS 服务器。 执行以下命令启动 Jar 包&#xff1a; 复制插入 java -jar /path/to/your/jar/file.jar复制插…...

法治智能起航 | 拓世法宝AI智慧政务一体机重塑法治格局,开启智能司法新篇章

在科技的巨轮推动下&#xff0c;我们的社会正快速迈向一个以数据和智能为核心的新时代。在这个波澜壮阔的变革中&#xff0c;人工智能&#xff08;AI&#xff09;显得尤为突出&#xff0c;它不仅是科技进步的象征&#xff0c;更是未来发展的助力者。 2023年&#xff0c;最高人…...

【华为云IaaS基础三件套之----计算ECS、网络EIP、存储EVS】

MD[华为云IaaS基础三件套----计算、网络、存储] 华为云IaaS基础三件套之----计算ECS、网络EIP、存储EVS 说明: 这里只是简单从计算/网络/存储&#xff0c;进行介绍&#xff0c;阐明云上对于云下的优势&#xff1b;因ECS是三者综合&#xff0c;故最后说明。 1.网络----弹性公…...

c语言数据结构---广义表

#include<stdio.h> #include<stdlib.h> typedef struct GNode{//广义表 int NodeTag; //标志域union{ char data;struct GNode *sublist;};struct GNode *next; }*PGNode,PG; void CreateGList(PGNode &GL) {char ch;scanf("%c", …...

2023.11.12使用flask对图片进行黑白处理(base64编码方式传输)

2023.11.12使用flask对图片进行黑白处理&#xff08;base64编码方式传输&#xff09; 由前端输入图片并预览&#xff0c;在后端处理图片后返回前端显示&#xff0c;可以作为图片处理的模板。 关键点在于对图片进行base64编码的转化。 使用Base64编码可以更方便地将图片数据嵌入…...

MATLAB中Filter Designer的使用以及XILINX Coefficient(.coe)File的导出

文章目录 Filter Designer的打开滤波器参数设置生成matlab代码生成XILINX Coefficient(.COE) File实际浮点数的导出官方使用教程 Filter Designer的打开 打开Filter Designer&#xff1a; 方法一&#xff1a;命令行中输入Filter Designer&#xff0c;再回车打开。 方法二&…...

js 深度学习(四)

函数 var test function test1(){var a 1,b2console.log(a,b)test1()//递归 } console.log(test.name) //test1 test1() //报错匿名函数表达式 函数自变量 var test function(){->匿名函数var a 1,b2console.log(a,b)test1()//递归 }var test function(a,b){var a 1,b2…...

leetcode刷题日记:121. Best Time to Buy and Sell Stock( 买卖股票的最佳时机)

题目给了我们一组数prices&#xff0c;其中prices[i]表示第i天的股票价格&#xff0c;需要我们求出买卖股票所能获得的最大收益。 我们的第一想法就是从算出每一种买卖股票的情况然后求出里面的最大值&#xff0c;这样我们就能得到最大收益是多少&#xff0c;但是这种情况过于复…...

Mac 本地部署thinkphp8【部署环境以及下载thinkphp】

PHP的安装以及环境变量配置 1 PHP安装&#xff1a;在终端输入brew install php 这里是PHP下载的最新的 如果提示‘brew’找不到&#xff0c;自己搜索安装吧&#xff0c; 不是特别难 2 环境变量配置 终端输入vim ~/.bash_profile 输入export PATH"/usr/local/Cellar/php/8.…...

【汽车电子】CAN总线分析仪使用介绍(PCAN/同星CAN卡)

本篇文章以CAN卡的使用为基本线索&#xff0c;介绍了在汽车电子领域涉及的一些CAN卡使用流程&#xff0c;搭配强大的上位机可以实现诸多功能。文章并没有局限于一种CAN卡&#xff0c;而是针对PCAN和同星的CAN卡分别以常用CAN报文收发以及诊断控制台实现这两种方向进行了CAN卡使…...

挑战杯推荐项目

“人工智能”创意赛 - 智能艺术创作助手&#xff1a;借助大模型技术&#xff0c;开发能根据用户输入的主题、风格等要求&#xff0c;生成绘画、音乐、文学作品等多种形式艺术创作灵感或初稿的应用&#xff0c;帮助艺术家和创意爱好者激发创意、提高创作效率。 ​ - 个性化梦境…...

国防科技大学计算机基础课程笔记02信息编码

1.机内码和国标码 国标码就是我们非常熟悉的这个GB2312,但是因为都是16进制&#xff0c;因此这个了16进制的数据既可以翻译成为这个机器码&#xff0c;也可以翻译成为这个国标码&#xff0c;所以这个时候很容易会出现这个歧义的情况&#xff1b; 因此&#xff0c;我们的这个国…...

(二)TensorRT-LLM | 模型导出(v0.20.0rc3)

0. 概述 上一节 对安装和使用有个基本介绍。根据这个 issue 的描述&#xff0c;后续 TensorRT-LLM 团队可能更专注于更新和维护 pytorch backend。但 tensorrt backend 作为先前一直开发的工作&#xff0c;其中包含了大量可以学习的地方。本文主要看看它导出模型的部分&#x…...

AirSim/Cosys-AirSim 游戏开发(四)外部固定位置监控相机

这个博客介绍了如何通过 settings.json 文件添加一个无人机外的 固定位置监控相机&#xff0c;因为在使用过程中发现 Airsim 对外部监控相机的描述模糊&#xff0c;而 Cosys-Airsim 在官方文档中没有提供外部监控相机设置&#xff0c;最后在源码示例中找到了&#xff0c;所以感…...

根目录0xa0属性对应的Ntfs!_SCB中的FileObject是什么时候被建立的----NTFS源代码分析--重要

根目录0xa0属性对应的Ntfs!_SCB中的FileObject是什么时候被建立的 第一部分&#xff1a; 0: kd> g Breakpoint 9 hit Ntfs!ReadIndexBuffer: f7173886 55 push ebp 0: kd> kc # 00 Ntfs!ReadIndexBuffer 01 Ntfs!FindFirstIndexEntry 02 Ntfs!NtfsUpda…...

MyBatis中关于缓存的理解

MyBatis缓存 MyBatis系统当中默认定义两级缓存&#xff1a;一级缓存、二级缓存 默认情况下&#xff0c;只有一级缓存开启&#xff08;sqlSession级别的缓存&#xff09;二级缓存需要手动开启配置&#xff0c;需要局域namespace级别的缓存 一级缓存&#xff08;本地缓存&#…...

redis和redission的区别

Redis 和 Redisson 是两个密切相关但又本质不同的技术&#xff0c;它们扮演着完全不同的角色&#xff1a; Redis: 内存数据库/数据结构存储 本质&#xff1a; 它是一个开源的、高性能的、基于内存的 键值存储数据库。它也可以将数据持久化到磁盘。 核心功能&#xff1a; 提供丰…...

如何配置一个sql server使得其它用户可以通过excel odbc获取数据

要让其他用户通过 Excel 使用 ODBC 连接到 SQL Server 获取数据&#xff0c;你需要完成以下配置步骤&#xff1a; ✅ 一、在 SQL Server 端配置&#xff08;服务器设置&#xff09; 1. 启用 TCP/IP 协议 打开 “SQL Server 配置管理器”。导航到&#xff1a;SQL Server 网络配…...

flow_controllers

关键点&#xff1a; 流控制器类型&#xff1a; 同步&#xff08;Sync&#xff09;&#xff1a;发布操作会阻塞&#xff0c;直到数据被确认发送。异步&#xff08;Async&#xff09;&#xff1a;发布操作非阻塞&#xff0c;数据发送由后台线程处理。纯同步&#xff08;PureSync…...

leetcode_69.x的平方根

题目如下 &#xff1a; 看到题 &#xff0c;我们最原始的想法就是暴力解决: for(long long i 0;i<INT_MAX;i){if(i*ix){return i;}else if((i*i>x)&&((i-1)*(i-1)<x)){return i-1;}}我们直接开始遍历&#xff0c;我们是整数的平方根&#xff0c;所以我们分两…...