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

L2-023 图着色问题 #DFS C++邻接矩阵存图

news 来源：原创 2025/9/2 10:33:33

文章目录

题目解读
- 输入格式
- 输出格式
思路
- Ac CODE
参考

题目解读

给定一个无向图V，询问是否可以用K种颜色为V中每一个顶点分配一种颜色，使得不会有两个相邻顶点具有同一种颜色

输入格式

第一行给出V,E,K，
分别代表无向图的顶点，边数，以及颜色数。
顶点和颜色都从1到V编号。
随后E行,每行表示一条边的两个端点。
随后给出正整数N，表示检查颜色分配方案的个数
最后N行，每行给出V个顶点的颜色
注意这个这里给出的V个顶点的颜色数量大于K,那么可直接输出No

输出格式

对每种颜色分配方案，如果是图着色问题的一个解则输出Yes，否则输出No，每句占一行。

思路

存好图之后对每一个没有遍历过的顶点进行遍历

Ac CODE

#include<bits/stdc++.h>using namespace std;const int N = 510;
int g[N][N];//邻接矩阵存图 
int color[N];//标记颜色
bool used[N];//标记数组,标记当前点是否遍历过 
int v,e,k,n;bool dfs(int u){//标记遍历过 used[u]=1;for(int i=1; i<=v; i++){//如果当前两个顶点有边 if(g[u][i]==1){//判断这两个顶点的颜色是否相同 if(color[u] == color[i]){cout<<"No\n";return 0;}//如果相连的边没有被遍历过,那么遍历 if(used[i]==0){//只要有一个不合法,那么就返回false if(dfs(i)==0)return 0;}}}//如果遍历完所有与该顶点相连的边都合法,那么返回1 return 1;
}int main(){//顶点点数，边数,颜色数。cin >> v >> e >> k;for(int i=0; i<e; i++){int x,y;cin >> x >> y;g[x][y]=g[y][x]=1;}cin >> n;//颜色分配方案个数 while(n--){//多组数据,要给used数组进行初始化赋值 memset(used,0,sizeof used);map<int,bool> temp;//遍历n个顶点for(int i=1; i<=v; i++){//读入当前顶点的颜色 cin>>color[i];//如果当前颜色找不到,那么存储进入map; if(temp.count(color[i])==0)temp[color[i]]=1;}//如果颜色总数大于k,那么直接就不合法 if(temp.size() != k){cout<<"No\n";continue;}else{for(int i=1; i<=v; i++){//如果当前顶点没有遍历过,那么从当前顶点开始遍历 if(used[i] == 0){if(dfs(i)==0)break;}if(i==v)cout<<"Yes\n";}}}return 0;
}

参考

B站up主–一天能吃五顿饭

🌻编写本篇文章目的是笔者想以输出的形式进行学习，顺便记录学习点滴🌻

🌹 如果本篇文章对你有帮助的话那就点个赞吧👍🌹

😇 本篇文章可能存在多处不足，如有修改意见，可以私信或者评论我哦 😇

在这里插入图片描述

L2-023 图着色问题 #DFS C++邻接矩阵存图

文章目录题目解读输入格式输出格式思路Ac CODE 参考题目解读给定一个无向图V，询问是否可以用K种颜色为V中每一个顶点分配一种颜色，使得不会有两个相邻顶点具有同一种颜色输入格式第一行给出V,E,K， 分别代表无向图的顶点，…...

编程日记 2025/9/2 10:33:33

架构下的按钮效果设置

以下是一个完整的跨QML/Qt Widgets的主题方案实现，包含对按钮阴影的统一管理： 一、项目结构 Project/ ├── core/ │ ├── thememanager.h │ └── thememanager.cpp ├── widgets/ │ ├── mainwindow.h │ ├── mainwindow.cpp …...

编程日记 2025/9/2 10:22:08

Unhandled exception: org.apache.poi.openxml4j.exceptions.InvalidFormatException

代码在main方法里面没有报错，在Controller里面就报错了。原来Controller类里面少了行代码 import org.apache.poi.openxml4j.exceptions.InvalidFormatException; 加上去就解决了。...

编程日记 2025/9/2 10:31:20

Vue2_Vue.js教程

目录一、Vue.js安装 1、独立版本 2、CDN 方法 3、npm 方法二、Vue Al编程助手三、Vue.js目录结构目录解析四、Vue.js 起步 1.如何定义数据对象和方法并渲染进页面五、Vue.js 模板语法插值文本_{{}} Html_v-html 指令属性_v-bind (数据传输工具)指令表…...

编程日记 2025/9/2 10:28:50

2025/4/2 心得

第一题题目描述给定1001个范围在[1,1000]的数字，保证只有1个数字重复出现2次，其余数字只出现1次。试用O(n)时间复杂度来求出出现2次的这个数字。不允许用数组输入格式第一行：一个整数1001； 第二行：1001个用…...

编程日记 2025/9/2 10:33:32

Deep Reinforcement Learning for Robotics翻译解读

a. 机器人能力 1 单机器人能力（Single-robot competencies） 运动能力（Mobility） 行走（Locomotion）导航（Navigation） 操作能力（Manipulation） 静态操作&…...

编程日记 2025/9/2 10:26:51

【Linux】日志模块实现详解

📢博客主页：https://blog.csdn.net/2301_779549673 📢博客仓库：https://gitee.com/JohnKingW/linux_test/tree/master/lesson 📢欢迎点赞 👍 收藏 ⭐留言 📝 如有错误敬请指正！ &…...

编程日记 2025/9/2 10:30:07

AT_abc212_d [ABC212D] Querying Multiset

链接：AT_abc212_d [ABC212D] Querying Multiset - 洛谷题目描述高橋君は何も書かれていないたくさんのボールと 1 つの袋を持っています。最初、袋は空で、高橋君は Q 回の操作を行います。それぞれの操作は以下の 3 種類のうちのいずれかです。操作 1 : ま…...

编程日记 2025/9/2 10:27:10

Android使用OpenGL和MediaCodec录制

目录一,什么是opengl 二,什么是Android OpenGL ES 三, OpenGL 绘制流程四, OpenGL坐标系五, OpenGL 着色器六, GLSL编程语言七,使用MediaCodec录制在Opengl中渲染架构八,代码实现 8.1 自定义渲染view继承GLSurfaceView 8.2 自定义渲染器TigerRender 8.3 创建编…...

编程日记 2025/8/27 11:39:07

Java 实现插入排序：[通俗易懂的排序算法系列之三]

引言大家好！欢迎继续关注我的排序算法系列。今天，我们要学习的是另一种非常基础且重要的排序算法——插入排序 (Insertion Sort)。插入排序的思路非常贴近我们日常整理扑克牌的方式，理解起来相对自然。虽然它在最坏情况下的效率不高&…...

编程日记 2025/9/2 10:22:59

HarmonyOS：WebView 控制及 H5 原生交互实现

一、效果展示二、技术栈技术栈： 编程语言：使用 TypeScript 进行开发，借助其类型系统提升代码的可读性与稳定性。框架与库：基于鸿蒙系统相关框架（如kit.ArkWeb、hadss/hmrouter&#xff09…...

编程日记 2025/9/2 10:23:00

250405-VSCode编辑launch.json实现Debug调试Open-WebUI

A. 最终效果根据__init__.py配置launch.json 根据中utils/chat.py中form_data的messages [{role: user, content: 唐老鸭}],可以找到用户输入，进而通过关键词或模型调用的方式，对敏感问题进行特殊处理。 B. 文件配置 launch.json // { // /…...

编程日记 2025/9/2 10:25:33

SQL Server 数据库实验报告

1.1 实验题目：索引和数据完整性的使用 1.2 实验目的： （1）掌握SQL Server的资源管理器界面应用； （2）掌握索引的使用； （3）掌握数据完整性的…...

编程日记 2025/8/28 4:13:13

【寻找Linux的奥秘】第三章：基础开发工具（上）

请君浏览前言1. 软件包管理器1.1 linux中安装软件1.2 yum的具体操作1.2.1 查找软件包1.2.2 安装软件1.2.3 卸载软件 1.3 小结 2. 编辑器vim2.1 vim的基本概念和操作2.2 命令模式的命令集光标定位其他命令模式切换（常用的） 2.3 末⾏模式的命令集2.4 小结…...

编程日记 2025/8/27 7:10:38

Photoshop 2025 Mac中文Ps图像编辑

Photoshop 2025 Mac中文Ps图像编辑文章目录 Photoshop 2025 Mac中文Ps图像编辑一、介绍二、效果三、下载一、介绍 Adobe Photoshop 2025 Mac版集成了多种强大的图像编辑、处理和创作功能。①强化了Adobe Sensei AI的应用，通过智能抠图、自动修复、图像生成等功能…...

编程日记 2025/8/28 13:53:06

#SVA语法滴水穿石# （004）关于 ended 和 triggered 用法

在 SystemVerilog 断言（SVA, SystemVerilog Assertions）中，ended 是一个用于序列（sequence）的关键字，它表示某个序列（sequence）在特定时间点已经成功匹配（即“结束”）。 ended 主要用于同步不同序列的时间关系，尤其是在多序列组合或属性（property）中需要对齐时…...

编程日记 2025/8/29 3:49:15

16.1Linux自带的LED灯驱动实验(知识)_csdn

前面我们都是自己编写 LED 灯驱动，其实像 LED 灯这样非常基础的设备驱动， Linux 内核已经集成了。 Linux 内核的 LED 灯驱动采用 platform 框架，因此我们只需要按照要求在设备树文件中添加相应的 LED 节点即可，本章我们就来学习如…...

编程日记 2025/8/31 13:13:28

普通类、抽象类和接口的区别

1. 普通类 (Concrete Class) 定义：完整的类，可以直接实例化特点： 可以包含属性、普通方法（有具体实现）和构造方法可以被直接实例化创建对象可以被继承（除非用final修饰） 示例&#xff1…...

编程日记 2025/8/29 7:54:56

使用 Elastic 实现端到端的大语言模型（LLM）可观测性：洞察生成式 AI 应用这个不透明的世界

作者：来自 Elastic Daniela Tzvetkova 及 Bahubali Shetti 在快速发展的人工智能领域，大语言模型（Large Language Models - LLMs）已成为创新的灯塔，为各行各业带来了前所未有的能力。从生成类人文本、翻译语言到提供个…...

编程日记 2025/8/30 0:58:36

15.2linux设备树下的platform驱动编写(程序)_csdn

我尽量讲的更详细，为了关注我的粉丝！！！ 修改设备树文件： 这个我们在上一章已经写过了，但是还是带着大家来重写一遍！ 1.打开pinctrl-stm32.c 这个文件： strict 成员变量默认为 true&…...

编程日记 2025/9/1 7:55:01

Java的Selenium的特殊元素操作与定位之window切换

当你要操作另外一个窗口页面的元素时，一定要注意先切换窗口切换方式:传入要操作窗口的name或者句柄handle driver.switchTo.window(nameOrHandle); 如何获取到窗口的句柄 driver.getWindowHandle();//获取当前操作窗口的句柄driver.getWindowHandles();//获取测…...

编程日记 2025/8/28 12:28:36

【Rust学习】Rust环境搭建和Rust基础语法

本文专栏：Rust学习目录一，Rust环境搭建 1，C环境安装 2，Rust下载 3，Rust安装 4，Rust环境检测二，创建Rust项目 1，rustc 2，cargo 三，输出到命令行 …...

编程日记 2025/8/30 20:35:45

在windows环境下通过docker-compose脚本自动创建mysql和redis

一、环境版本在windows环境下通过docker容器运行各种服务，使用的软件版本如下： docker desktop ：V4.39.0 【docker的安装环境设置略】 mysql：9.2 redis：7.4.2 二、各配置文件 1.已经解决了字符集和排序规则问题造成…...

编程日记 2025/8/29 7:30:05

【玩泰山派】2、制作buildroot镜像，并烧录

文章目录前言制作buildroot镜像过程搭建环境（docker版）下载泰山派开发的sdk利用制作的镜像和下载的sdk去启动开发docker容器编译buildroot镜像参考前言泰山派官方提供了不少现成的镜像但是都买了泰山派了，肯定是想自己编译折腾下&…...

编程日记 2025/8/26 23:00:09

实验二 VLAN 的配置与应用

一、实验目的 1. 熟悉 VLAN 和 PORT VLAN 的原理； 2. 熟悉华为网络模拟器的使用； 3. 掌握网络拓扑图的绘制； 4. 掌握单交换机内 VLAN 的配置。二、实验设备 PC、华为模拟器 ENSP。三、实验步骤知识准备：VLAN 和 PORT V…...

编程日记 2025/8/23 5:12:40

【C/C++算法】蓝桥杯之递归算法（如何编写想出递归写法）

绪论：冲击蓝桥杯一起加油！！ 每日激励：“不设限和自我肯定的心态：I can do all things。 — Stephen Curry” 绪论： ———————— 早关注不迷路，话不多说安全带系好，发车啦&am…...

编程日记 2025/8/30 12:35:58

coding ability 展开第九幕（位运算——进阶篇）超详细！！！！

文章目录前言丢失的数字两整数之和只出现一次的数字II消失的两个数字总结前言上一篇博客，我们已经把位运算的基础知识，以及基本运算都掌握啦上次的习题还是让人意犹未尽，今天我们来尝试一下难一点的题目位运算熟练起来真的让人觉得做题是…...

编程日记 2025/8/29 18:30:34

Python实现NOA星雀优化算法优化随机森林回归模型项目实战

说明：这是一个机器学习实战项目（附带数据代码文档视频讲解），如需数据代码文档视频讲解可以直接到文章最后关注获取。 1.项目背景在现代数据科学领域，回归分析是解决预测问题的核心工具之一。然而，在面对复…...

编程日记 2025/8/25 22:20:14

蓝桥云客--浓缩咖啡液

4.浓缩咖啡液【算法赛】 - 蓝桥云课问题描述蓝桥杯备赛选手小蓝最近刷题刷到犯困，决定靠咖啡续命。他手上有 N 种浓缩咖啡液，浓度分别是 A1%, A2%, …, AN%，每种存货都是无限的。为了提神又不炸脑，小蓝需要按比例混合这…...

编程日记 2025/8/31 14:50:16

异常【C++】

文章目录异常异常的概念和基本语法异常的三个关键字： 异常抛出和被接收的过程异常的再次抛出再次抛出被非catch（...）捕捉到的异常再次抛出被catch（...）捕捉到的异常异常规范异常安全异常的优缺点优点缺点总结&#x…...

编程日记 2025/8/29 4:08:47

关于图片分类任务的猜想 | 撰写论文 paper

关于图片分类任务的猜想 | 撰写论文 paper 背景Yolo 是一次巨大的飞跃过滤无关的特征Yolo 的问题背景在计算视觉领域，有几个关键的演变。 1）CNN 卷积的出现，这是一个大的创新； 2）从卷积到 AlexNet ，是更…...

编程日记 2025/9/1 4:53:50

路由器和交换机

路由器和交换机分别位于OSI模型和TCP/IP模型的不同网络层次，具体对比如下： 1. 路由器（Router） 所属层级： OSI模型：网络层（第3层）TCP/IP模型：网络互联层（Int…...

编程日记 2025/8/23 4:57:35

jEasyUI 表单验证

jEasyUI 表单验证引言 jEasyUI 是一款流行的 jQuery UI 扩展库，它提供了丰富的 UI 组件和交互效果，极大地方便了前端开发工作。在 jEasyUI 中，表单验证是一个非常重要的功能，它可以帮助开发者确保用户输入的数据符合预期的格式和规则。本文将详细介绍 jEasyUI 表单验证的…...

编程日记 2025/9/2 8:23:53

PIKE 助力知识库进阶：多模型协作下的精准信息 “捕手”

PIKE（通常指的是字节跳动提出的一种技术）增强检索知识库是一种结合了先进的信息检索技术和知识库管理的系统。它旨在提高知识检索的准确性、效率和召回率，以更好地满足用户对知识的需求。特点和工作原理数据增强 ：对知识库中…...

编程日记 2025/8/29 22:47:16

使用Ubuntu18恢复群晖nas硬盘数据外接usb

使用Ubuntu18恢复群晖nas硬盘数据外接usb 1. 接入硬盘2.使用Ubuntu183.查看nas硬盘信息3. 挂载nas3.1 挂载损坏nas硬盘(USB)3.2 挂载当前运行的nas 4. 拷贝数据分批传输 5. 新旧数据对比 Synology NAS 出现故障，DS DiskStation损坏，则可以使用计算机和 U…...

编程日记 2025/8/28 11:23:18

Dify票据识别遇到的分支判断不准确问题

已测试这篇文章中 https://zhuanlan.zhihu.com/p/5465385787 使用多分支条件判断使用不同的大模型识别图片内容发现了细节问题。在使用时若不注意，分支会出现走向不准的问题。需要关注部分下方红框处。1，2后不能跟点。否则会出问。除此之外&#xff0…...

编程日记 2025/8/18 0:39:19

Flutter学习总结之Android渲染对比

一、Android 界面渲染机制（基于原生 View 体系） 1. 核心渲染流程（源码级解析） 三阶段渲染流程（ViewRootImpl驱动）： Measure 阶段（measure()）： View调用onMea…...

编程日记 2025/8/29 23:01:31

Media streaming is a huge topic with a bunch of scattered technologies, protocols, and formats. You may feel like hearing fragments without seeing the big picture. Let’s build that mental map together — here’s a high-level overview that connects everyt…...

编程日记 2025/8/27 17:40:48

文章目录

题目解读

输入格式

输出格式

思路

Ac CODE

参考

相关文章：