当前位置: 首页 > 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;设计并开发实用、方便的应用程序…...

利用最小二乘法找圆心和半径

#include <iostream> #include <vector> #include <cmath> #include <Eigen/Dense> // 需安装Eigen库用于矩阵运算 // 定义点结构 struct Point { double x, y; Point(double x_, double y_) : x(x_), y(y_) {} }; // 最小二乘法求圆心和半径 …...

Flask RESTful 示例

目录 1. 环境准备2. 安装依赖3. 修改main.py4. 运行应用5. API使用示例获取所有任务获取单个任务创建新任务更新任务删除任务 中文乱码问题&#xff1a; 下面创建一个简单的Flask RESTful API示例。首先&#xff0c;我们需要创建环境&#xff0c;安装必要的依赖&#xff0c;然后…...

Lombok 的 @Data 注解失效,未生成 getter/setter 方法引发的HTTP 406 错误

HTTP 状态码 406 (Not Acceptable) 和 500 (Internal Server Error) 是两类完全不同的错误&#xff0c;它们的含义、原因和解决方法都有显著区别。以下是详细对比&#xff1a; 1. HTTP 406 (Not Acceptable) 含义&#xff1a; 客户端请求的内容类型与服务器支持的内容类型不匹…...

进程地址空间(比特课总结)

一、进程地址空间 1. 环境变量 1 &#xff09;⽤户级环境变量与系统级环境变量 全局属性&#xff1a;环境变量具有全局属性&#xff0c;会被⼦进程继承。例如当bash启动⼦进程时&#xff0c;环 境变量会⾃动传递给⼦进程。 本地变量限制&#xff1a;本地变量只在当前进程(ba…...

23-Oracle 23 ai 区块链表(Blockchain Table)

小伙伴有没有在金融强合规的领域中遇见&#xff0c;必须要保持数据不可变&#xff0c;管理员都无法修改和留痕的要求。比如医疗的电子病历中&#xff0c;影像检查检验结果不可篡改行的&#xff0c;药品追溯过程中数据只可插入无法删除的特性需求&#xff1b;登录日志、修改日志…...

UDP(Echoserver)

网络命令 Ping 命令 检测网络是否连通 使用方法: ping -c 次数 网址ping -c 3 www.baidu.comnetstat 命令 netstat 是一个用来查看网络状态的重要工具. 语法&#xff1a;netstat [选项] 功能&#xff1a;查看网络状态 常用选项&#xff1a; n 拒绝显示别名&#…...

【机器视觉】单目测距——运动结构恢复

ps&#xff1a;图是随便找的&#xff0c;为了凑个封面 前言 在前面对光流法进行进一步改进&#xff0c;希望将2D光流推广至3D场景流时&#xff0c;发现2D转3D过程中存在尺度歧义问题&#xff0c;需要补全摄像头拍摄图像中缺失的深度信息&#xff0c;否则解空间不收敛&#xf…...

Auto-Coder使用GPT-4o完成:在用TabPFN这个模型构建一个预测未来3天涨跌的分类任务

通过akshare库&#xff0c;获取股票数据&#xff0c;并生成TabPFN这个模型 可以识别、处理的格式&#xff0c;写一个完整的预处理示例&#xff0c;并构建一个预测未来 3 天股价涨跌的分类任务 用TabPFN这个模型构建一个预测未来 3 天股价涨跌的分类任务&#xff0c;进行预测并输…...

【算法训练营Day07】字符串part1

文章目录 反转字符串反转字符串II替换数字 反转字符串 题目链接&#xff1a;344. 反转字符串 双指针法&#xff0c;两个指针的元素直接调转即可 class Solution {public void reverseString(char[] s) {int head 0;int end s.length - 1;while(head < end) {char temp …...

Robots.txt 文件

什么是robots.txt&#xff1f; robots.txt 是一个位于网站根目录下的文本文件&#xff08;如&#xff1a;https://example.com/robots.txt&#xff09;&#xff0c;它用于指导网络爬虫&#xff08;如搜索引擎的蜘蛛程序&#xff09;如何抓取该网站的内容。这个文件遵循 Robots…...