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

二分图-染色法-dfs

1.判断一个图是否是二分图当且仅当图中不包含奇数环
2. dfs当前边为1 他的临边为2 看是否满足条件
3. 注意图有可能不是连通图

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;public class BinaryGraph {private static int N = 100010;//还没有进行初始化!private static int[] h = new int[N];private static int[] e = new int[N];private static int[] ne = new int[N];private static int idx;private static  int[] colors = new int [N];private static int n;private static int m;private static boolean flag = true;public static void add(int a, int b){e[idx] = b;ne[idx] = h[a];h[a] = idx++;}public static boolean dfs(int a, int c){colors[a] = c;for(int i = h[a]; i != -1; i = ne[i] ){int j = e[i];//如果没有对这个点进行染色if(colors[j] == 0){dfs(j,3 - c);}else if(colors[j] == c){flag = false;return false;}}return true;}public static void main(String[] args) throws IOException {BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));String[] s = reader.readLine().split(" ");n = Integer.parseInt(s[0]);m = Integer.parseInt(s[1]);Arrays.fill(h,-1); //对h进行初始化for(int i = 0; i < m; i++){String[] s1 = reader.readLine().split(" ");int u = Integer.parseInt(s1[0]);int v = Integer.parseInt(s1[1]);//无向图add(u,v);add(v,u);}for(int i = 1; i <= n; i++){//当前点没有被染色if(colors[i] == 0){//染色时出现冲突if(!dfs(i,1)){flag = false;break;}}}if(flag){System.out.println("Yes");}else System.out.println("No");}
}

相关文章:

二分图-染色法-dfs

1.判断一个图是否是二分图当且仅当图中不包含奇数环 2. dfs当前边为1 他的临边为2 看是否满足条件 3. 注意图有可能不是连通图 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays;public class BinaryG…...

SQL优化案例教程0基础(小白必看)

前提准备&#xff1a;本案例准备了100W的数据进行SQL性能测试&#xff0c;数据库采用的是MySQL&#xff0c; 总共介绍了常见的14种SQL优化方式&#xff0c;每一种优化方式都进行了实打实的测试&#xff0c; 逐行讲解&#xff0c;通俗易懂&#xff01; 一、前提准备 提前准备一…...

webpack(一)模块化

模块化演变过程 阶段一&#xff1a;基于文件的划分模块方式 概念&#xff1a;将每个功能和相关数据状态分别放在单独的文件里 约定每一个文件就是一个单独的模块&#xff0c;使用每个模块&#xff0c;直接调用这个模块的成员 缺点&#xff1a;所有的成员都可以在模块外被访问和…...

基于Java+SpringBoot+Vue前后端分离人力资源管理系统设计和实现

博主介绍&#xff1a;✌全网粉丝30W,csdn特邀作者、博客专家、CSDN新星计划导师、Java领域优质创作者,博客之星、掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域和毕业项目实战✌ &#x1f345;文末获取源码联系&#x1f345; &#x1f447;&#x1f3fb; 精彩专…...

安装配置mariadb

记录下安装配置mariadb的经历。 环境&#xff1a;ubuntu22 一、apt在线安装 apt代理配置 APT是Ubuntu系统中用于安装和升级软件包的工具&#xff0c;如果本地没有可用的软件包&#xff0c;APT将会连接到远程软件包服务器下载软件包。在某些情况下&#xff0c;用户需要将APT的…...

Ant Design Vue 日期选择器DatePicker传给后台日期参数格式问题

花了一个下午才解决&#xff0c;官方组件文档里面是没有处理方案说明的。 项目版本&#xff1a;Ant Design Vue 2.0.2 前端部分代码&#xff1a; <template><a-modal:visible"visible":width"windowWidth":height"800":title"tit…...

springboot1.5.12升级至2.6.15

首先&#xff0c;加入springboot升级大版本依赖&#xff0c;会在升级过程中打印出错日志提示&#xff08;升级完毕可去除&#xff09; <dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-properties-migrator</art…...

Android Event事件分发(新版本)

之前写过一个方案&#xff08;添加链接描述&#xff09;&#xff0c;突然觉得很麻烦&#xff0c;于是有了新的方案&#xff1a; 首先先说要解决的问题&#xff1a; 当父布局能滑动&#xff0c;子View也能滑动&#xff0c;就会出现滑动冲突 解决思路&#xff1a;我们按下子Vie…...

可控生成:ControlNet原理

🤗关注公众号funNLPer体验更佳阅读🤗 论文:Adding Conditional Control to Text-to-Image Diffusion Models 代码:lllyasviel/ControlNet 简单来说ControlNet希望通过输入额外条件来控制大型图像生成模型,使得图像生成模型根据可控。 文章目录 1. 动机2. ControlNet原理…...

【极客时间】MySQL 必知必会-20230901

03 | 表&#xff1a;怎么创建和修改数据表&#xff1f; 新增数据表 CREATE DATABASE demo;CREATE TABLE goodsmaster (barcode TEXT,goodsname TEXT,price DOUBLE, itemnumber INT PRIMARY KEY AUTO_INCREMENT);INSERT INTO demo.goodsmaster (barcode, goodsname,price) VAL…...

53 个 CSS 特效 3(完)

53 个 CSS 特效 3&#xff08;完&#xff09; 前两篇地址&#xff1a; 53 个 CSS 特效 153 个 CSS 特效 2 这里是第 33 到 53 个&#xff0c;很多内容都挺重复的&#xff0c;所以这里解释没之前的细&#xff0c;如果漏了一些之前的笔记会补一下&#xff0c;写过的就会跳过。…...

简单数学题:找出最大的可达成数字

来看一道简单的数学题&#xff1a;力扣2769. 找出最大的可达成数字 题目描述的花里胡哨&#xff0c;天花乱坠&#xff0c;但这道题目非常简单。我们最多执行t次操作&#xff0c;只需每次操作都让x-1&#xff0c;让num1&#xff0c;执行t次操作后&#xff0c;x就变为xt&#xff…...

[C++ 网络协议] 套接字的多种可选项

目录 1. 套接字的可选项 2. 获取/设置套接字可选项 2.1 getsockopt函数&#xff08;获取套接字可选项&#xff09; 2.2 setsockopt函数&#xff08;设置套接字可选项&#xff09; 3. 常用套接字可选项 3.1 SOL_SOCKET协议层的SO_TYPE可选项 3.2 SOL_SOCKET协议层的SO_SN…...

2022年03月 C/C++(五级)真题解析#中国电子学会#全国青少年软件编程等级考试

第1题:数字变换 给定一个包含 5 个数字(0-9)的字符串, 例如 “02943”, 请将“12345”变换到它。 你可以采取 3 种操作进行变换 (1)交换相邻的两个数字 (2)将一个数字加 1。 如果加 1 后大于 9, 则变为 0 (3)将一个数字加倍。 如果加倍后大于 9,则将其变为加倍后的…...

***数据转换中常用的两个函数 sscanf,sprintf

1、sscanf将字符串转换成想要的整数或浮点数 (HMI屏中输入浮点数据,到mcu后要转换成对应的浮点数据) sscanf(“0.9”,“%f”,getData) /*! \brief 文本控件通知 \details 当文本通过键盘更新(或调用GetControlValue)时,执行此函数 \details 文本控件的内容以字符串形…...

软件工程(十九) 软件测试

软件测试主要了解软件测试的方法和软件的调试。 1、软件测试方法 1.1、测试基本思想 尽早、不断的进行测试 在V模型其实已经凸显出这种思想了程序员避免测试自己设计的程序 因为测试自己设计的程序,其实是不容易发现问题的,因为人从本质上都不愿意找自己的茬。而且由于你的…...

go中读写锁(rwmutex)源码解读实现原理

go读写锁的实现原理 1、RWMutex读写锁的概念 读写锁也就是我们所使用的RWMutex&#xff0c;其实是对于go本身的mutex做的一个拓展&#xff0c;当一个goroutine获得了读锁后&#xff0c;其他goroutine同样可以获得读锁&#xff0c;但是不能获得写锁。相反&#xff0c;当一个go…...

【人工智能】—_深度优先搜索、代价一致搜索、深度有限搜索、迭代深度优先搜索、图搜索

【人工智能】无信息搜索—BFS 、代价一致、DFS、深度受限、迭代深入深度优先、图搜索 什么是搜索 搜索问题是指既不能通过数学建模解决&#xff0c;又没有其他算法可以套用或者非遍历所有情况才能得出正确结果。这时就需要采用搜索算法来解决问题。搜索就是一种通过穷举所有解…...

uni-app 客服按钮可上下拖动动

项目需求&#xff1a; 因为悬浮客服有时候会遮挡住界面内容&#xff0c;故需要对悬浮的气泡弹窗做可拖动操作 movable-area&#xff1a;可拖动区域 movable-view&#xff1a;可移动的视图容器&#xff0c;在页面中可以拖拽滑动或双指缩放。 属性说明 属性名类型默认值说…...

基于Android的旅游管理系统 微信小程序

随着网络科技的发展&#xff0c;移动智能终端逐渐走进人们的视线&#xff0c;相关应用越来越广泛&#xff0c;并在人们的日常生活中扮演着越来越重要的角色。因此&#xff0c;关键应用程序的开发成为影响移动智能终端普及的重要因素&#xff0c;设计并开发实用、方便的应用程序…...

设计模式和设计原则回顾

设计模式和设计原则回顾 23种设计模式是设计原则的完美体现,设计原则设计原则是设计模式的理论基石, 设计模式 在经典的设计模式分类中(如《设计模式:可复用面向对象软件的基础》一书中),总共有23种设计模式,分为三大类: 一、创建型模式(5种) 1. 单例模式(Sing…...

Cloudflare 从 Nginx 到 Pingora:性能、效率与安全的全面升级

在互联网的快速发展中&#xff0c;高性能、高效率和高安全性的网络服务成为了各大互联网基础设施提供商的核心追求。Cloudflare 作为全球领先的互联网安全和基础设施公司&#xff0c;近期做出了一个重大技术决策&#xff1a;弃用长期使用的 Nginx&#xff0c;转而采用其内部开发…...

Python ROS2【机器人中间件框架】 简介

销量过万TEEIS德国护膝夏天用薄款 优惠券冠生园 百花蜂蜜428g 挤压瓶纯蜂蜜巨奇严选 鞋子除臭剂360ml 多芬身体磨砂膏280g健70%-75%酒精消毒棉片湿巾1418cm 80片/袋3袋大包清洁食品用消毒 优惠券AIMORNY52朵红玫瑰永生香皂花同城配送非鲜花七夕情人节生日礼物送女友 热卖妙洁棉…...

【Linux】Linux 系统默认的目录及作用说明

博主介绍&#xff1a;✌全网粉丝23W&#xff0c;CSDN博客专家、Java领域优质创作者&#xff0c;掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域✌ 技术范围&#xff1a;SpringBoot、SpringCloud、Vue、SSM、HTML、Nodejs、Python、MySQL、PostgreSQL、大数据、物…...

C++课设:简易日历程序(支持传统节假日 + 二十四节气 + 个人纪念日管理)

名人说:路漫漫其修远兮,吾将上下而求索。—— 屈原《离骚》 创作者:Code_流苏(CSDN)(一个喜欢古诗词和编程的Coder😊) 专栏介绍:《编程项目实战》 目录 一、为什么要开发一个日历程序?1. 深入理解时间算法2. 练习面向对象设计3. 学习数据结构应用二、核心算法深度解析…...

鸿蒙HarmonyOS 5军旗小游戏实现指南

1. 项目概述 本军旗小游戏基于鸿蒙HarmonyOS 5开发&#xff0c;采用DevEco Studio实现&#xff0c;包含完整的游戏逻辑和UI界面。 2. 项目结构 /src/main/java/com/example/militarychess/├── MainAbilitySlice.java // 主界面├── GameView.java // 游戏核…...

用神经网络读懂你的“心情”:揭秘情绪识别系统背后的AI魔法

用神经网络读懂你的“心情”:揭秘情绪识别系统背后的AI魔法 大家好,我是Echo_Wish。最近刷短视频、看直播,有没有发现,越来越多的应用都开始“懂你”了——它们能感知你的情绪,推荐更合适的内容,甚至帮客服识别用户情绪,提升服务体验。这背后,神经网络在悄悄发力,撑起…...

大模型——基于Docker+DeepSeek+Dify :搭建企业级本地私有化知识库超详细教程

基于Docker+DeepSeek+Dify :搭建企业级本地私有化知识库超详细教程 下载安装Docker Docker官网:https://www.docker.com/ 自定义Docker安装路径 Docker默认安装在C盘,大小大概2.9G,做这行最忌讳的就是安装软件全装C盘,所以我调整了下安装路径。 新建安装目录:E:\MyS…...

CppCon 2015 学习:Reactive Stream Processing in Industrial IoT using DDS and Rx

“Reactive Stream Processing in Industrial IoT using DDS and Rx” 是指在工业物联网&#xff08;IIoT&#xff09;场景中&#xff0c;结合 DDS&#xff08;Data Distribution Service&#xff09; 和 Rx&#xff08;Reactive Extensions&#xff09; 技术&#xff0c;实现 …...

Qwen系列之Qwen3解读:最强开源模型的细节拆解

文章目录 1.1分钟快览2.模型架构2.1.Dense模型2.2.MoE模型 3.预训练阶段3.1.数据3.2.训练3.3.评估 4.后训练阶段S1: 长链思维冷启动S2: 推理强化学习S3: 思考模式融合S4: 通用强化学习 5.全家桶中的小模型训练评估评估数据集评估细节评估效果弱智评估和民间Arena 分析展望 如果…...