搜索与图论——染色法判定二分图

一个图是二分图当且仅当这个图中不含奇数环

由于图中没有奇数环,所以染色过程中一定没有矛盾

所以一个二分图一定可以成功被二染色,反之在二染色的过程中出现矛盾的图中一定有奇数环,也就一定不是二分图

#include<iostream>
#include<algorithm>
#include<cstring>using namespace std;const int N = 100010, M = 200010;int n, m;
int h[N], e[M], ne[M], idx;
int color[N]; //color[i]代表i点有没有被染色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; //记录当前点的颜色是cfor(int i = h[u]; i != -1; i = ne[i])//遍历当前点的邻点{int j = e[i];if(!color[j]) //如果该点没有被染色{if(!dfs(j, 3 - c)) return false; //有1、2两种颜色,3-1=2,3-2=1,能把邻点染成与u点不同的颜色}else if(color[j] == c) return false; //如果u的邻点的颜色等于u的颜色}return true;
}int main()
{cin >> n >> m;memset(h, -1, sizeof h);while(m -- ){int a, b;cin >> a >> b;add(a, b), add(b, a); //无向边}bool flag = true; //染色过程中是否有矛盾发生for(int i = 1; i <= n; i ++ ){if(!color[i]) //如果该点没有被染色{if(!dfs(i, 1)) //如果bfs i点时返回false{flag = false;break;}}}if(flag) cout << "Yes" << endl;else cout << "No" << endl;return 0;
}

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

http和https的工作原理是什么?

HTTP&#xff08;HyperText Transfer Protocol&#xff09;和HTTPS&#xff08;HyperText Transfer Protocol Secure&#xff09;是两种用于在互联网上传输数据的主要协议&#xff0c;它们均用于在客户端&#xff08;通常是Web浏览器&#xff09;与服务器之间交换信息。尽管它们…

NSSCTF Round#20 Basic 真亦假,假亦真 CSDN_To_PDF V1.2 出题笔记 (附wp+源码)

真亦假&#xff0c;假亦真 简介&#xff1a;java伪造php一句话马。实则信息泄露一扫就出&#xff0c;flag在/flag里面。 题目描述&#xff1a;开开心心签个到吧&#xff0c;祝各位师傅们好运~ 静态flag&#xff1a;NSS{Checkin_h4v3_4_g00D_tINNe!} /路由显示 <?php e…

Radash一款JavaScript最新的实用工具库,Lodash的平替!

文章目录 Lodash 的痛点进入正题--Radash特点 举例几个常用的api 一说lodash应该大部分前端同学都知道吧&#xff0c;陪伴我们好多年的JavaScript工具库&#xff0c;但是自从 ES6 出现后就慢慢退出前端人的视线&#xff0c;能ES6写的代码绝对不会用Lodash&#xff0c;也不是完全…

住宅IP是什么?与机房IP有哪些区别?

随着互联网的普及和发展&#xff0c;不同类型的IP地址在网络世界中扮演着重要角色。在网络架构中&#xff0c;机房IP和住宅IP是两种常见的IP类型&#xff0c;它们各有优劣&#xff0c;适用于不同的场景和需求。本文将对机房IP和住宅IP进行技术对比&#xff0c;并给出选择合适IP…

vue项目使用eletron将打包成桌面应用(.exe)

vue项目使用eletron将打包成桌面应用(.exe) 1.前期准备 两个项目&#xff1a; 1、自己用vue cli创建的项目 2、第二个是去gitee将案例clone下来 案例地址 https://gitee.com/qingplus/electron-quick-start.git 2、测试案例是否可以正常运行 # 进入项目 cd electron-quick-…

kubernetes负载均衡资源-Ingress

一、Ingress概念 1.1 Ingress概念 使用NodePort类型的Service可以将集群内部服务暴露给集群外部客广端,但使用这种类型Service存在如下几个问题。 1、一个端口只能一个服务使用,所有通过NodePort暴露的端口都需要提前规划;2、如果通过NodePort暴露端口过多,后期维护成本太…

IPv6-重定向,PMTU,GRE隧道

IPv6-重定向&#xff0c;PMTU&#xff08;路径最大传输单元&#xff09;&#xff0c;GRE隧道&#xff08;Generic Routing Encapsulation&#xff0c;通用路由封装协议&#xff09; 重定向过程 触发重定向的条件&#xff1a; 1、报文的入接口&#xff0c;等于自身路由之后的…

ubuntu2204配置zabbix6.4高可用

zabbix6.4-HA 配置keepalived配置haproxy数据库高可用配置zabbix-server配置proxy配置客户端agent 本实验VMware搭建zabbix6.4高可用集群&#xff0c;搭配haproxykeepalived。 master&#xff0c;node节点搭建haproxykeepalibed主备并配置vip地址 三台控制节点搭建数据库高可用…

Pytorch 下载失败原因

错误信息&#xff1a; ERROR: Could not find a version that satisfies the requirement torch (from versions: none) ERROR: No matching distribution found for torch 解决方案&#xff1a; 在官网看到&#xff0c;它需要python3.8-3.11的环境。过高和过低的版本都不…

微信小程序备案流程详细操作指南

自2023年9月1日起&#xff0c;所有新上架的微信小程序均需事先完成备案手续&#xff0c;方能成功上线。而对于已经上架的存量小程序&#xff0c;也需要在2024年3月31日前完成备案工作。若在规定时间内未完成备案&#xff0c;平台将依据备案相关规定&#xff0c;自2024年4月1日起…

金三银四面试题(八):JVM常见面试题(2)

今天我们继续探讨常见的JVM面试题。这些问题不比之前的问题庞大&#xff0c;多用于面试中​JVM部分的热身运动&#xff0c;开胃菜&#xff0c;但是大家已经要认真准备。 JRE、JDK、JVM 及JIT 之间有什么不同&#xff1f; JRE 代表Java 运行时&#xff08;Java run-time&#…

ESP8266 控制 LED 亮灭

一、引脚对应 二、按键控制 LED 亮灭 2.1样例1 #include <ESP8266WiFi.h>const int ledPin D2; // LED 连接到 D2 引脚 const int keyPin D4; // 按键连接到 D4 引脚volatile bool flag false; // 记录 LED 状态的标志// 外部中断处理函数 ICACHE_RAM_ATTR void han…

(原型与原型链)前端八股文修炼Day5

一 原型链的理解 原型链定义&#xff1a; 原型链是 JavaScript 中实现对象继承的关键机制之一&#xff0c;它是一种对象之间的关系&#xff0c;通过这种关系&#xff0c;一个对象可以继承另一个对象的属性和方法。 原型链的组成&#xff1a; 每个对象都有一个指向另一个对象的…

C# 微软官方学习文档

链接&#xff1a;https://learn.microsoft.com/zh-cn/dotnet/csharp/ 在C#的学习过程中&#xff0c;我们可以参考微软官方的学习文档。它是一个免费的学习平台&#xff0c;提供了丰富的C#学习路径和教程&#xff08;如下图&#xff09;&#xff0c;对我们入门到高级应用开发都…

汇总:五个开源的Three.js项目

Three.js 是一个基于 WebGL 的 JavaScript 库&#xff0c;它提供了一套易于使用的 API 用来在浏览器中创建和显示 3D 图形。通过抽象和简化 WebGL 的复杂性&#xff0c;Three.js 使开发者无需深入了解 WebGL 的详细技术就能够轻松构建和渲染3D场景、模型、动画、粒子系统等。 T…

【自动装箱以及包装类的缓存】⭐️通过具体案例看下每种包装类的不同结果

目录 前言 一、自动装箱与拆箱&#xff08;以 Integer 包装类为例&#xff09; 二、再来看看几个示例 ​编辑三、Double ,Float 类型亦是如此吗&#xff1f; 前言 小伙伴们大家好&#xff0c;日常使用业务层方面的代码居多&#xff0c;但也不可忘了基本的一些代码格式以及原…

npm淘宝镜像源更新

目录 前情提要&#xff1a; 背景&#xff1a; 镜像源更新&#xff1a; 清楚缓存&#xff1a; 直接切换镜像源&#xff1a; 注&#xff1a;npm 补充&#xff1a; 错误解释&#xff1a; 解决方法&#xff1a; 前情提要&#xff1a; 2024 /1 /22 &#xff0c;registry.npm…

理解游戏服务器架构-逻辑底层架构

目录 前言 什么是逻辑底层架构 逻辑底层架构的职责 1&#xff09;Thread-线程 线程管理 线程通讯 线程安全锁机制 2&#xff09;Network-网络 网络模型 网络消息协议 断线重连 网络安全 防范重复消息 防范篡改消息内容 防范篡改内存数据 网络承载 3&#xff0…

HarmonyOS 应用开发之FA模型启动Stage模型UIAbility

本文介绍FA模型的三种应用组件如何启动Stage模型的UIAbility组件。 PageAbility启动UIAbility 在PageAbility中启动UIAbility和在PageAbility中启动PageAbility的方式完全相同。 import featureAbility from ohos.ability.featureAbility; import { BusinessError } from oh…

阿里云2核4G服务器租用价格,支持多少人在线?

阿里云2核4G服务器多少钱一年&#xff1f;2核4G配置1个月多少钱&#xff1f;2核4G服务器30元3个月、轻量应用服务器2核4G4M带宽165元一年、企业用户2核4G5M带宽199元一年。可以在阿里云CLUB中心查看 aliyun.club 当前最新2核4G服务器精准报价、优惠券和活动信息。 阿里云官方2…