1154 Vertex Coloring (25 分)

2024-03-04 16:32
文章标签 25 1154 vertex coloring

本文主要是介绍1154 Vertex Coloring (25 分),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

版本2

图的深搜

#include <cstdio>
#include <iostream>
#include <vector>
#include <cstring>
#include <queue> 
#include <unordered_set>
#include <algorithm>
using namespace std;
const int N = 1e4+5;
vector<int> G[N];
bool vis[N]; 
int n, m;
int color[N];
bool flag;
void dfs(int r){ if(flag) return; //如果着色冲突则返回 vis[r] = true;for(int i = 0; i < G[r].size(); i++){int v = G[r][i];if(color[r] == color[v]) flag = true;if(flag) return; if(!vis[v]) dfs(v);}
}
int main(){scanf("%d%d", &n, &m);int u, v;while(m--){scanf("%d%d", &u, &v);G[u].push_back(v);G[v].push_back(u); //无向图 }int k;scanf("%d", &k);while(k--){unordered_set<int> st;flag = false;for(int i = 0; i < n; i++) scanf("%d", color+i), st.insert(color[i]);memset(vis, 0, sizeof vis);for(int i = 0; i < n; i++){if(!vis[i]) dfs(i);}if(!flag) printf("%d-coloring\n", st.size());else puts("No");}return 0;
}

版本1

遍历所有边,不需要用深搜,只需要把读入的每条边再循环一遍就ok了

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e4+5;
int arr[maxn];
struct node{int u,v;
}E[maxn];set<int> st;int main(){int n,m,u,v;scanf("%d%d",&n,&m);for(int i=0; i<m; i++){scanf("%d%d",&u,&v);E[i].u = u;E[i].v = v;}int k;scanf("%d",&k);while(k--){memset(arr,-1,sizeof(arr));st.clear();for(int i=0;i<n;i++){scanf("%d",&arr[i]);st.insert(arr[i]); }int flag=0;for(int i=0;i<m;i++){if(arr[E[i].u] == arr[E[i].v]){flag=1;break;}}if(flag){printf("No\n");}else printf("%d-coloring\n",st.size());}return 0;
}

这篇关于1154 Vertex Coloring (25 分)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/773765

相关文章

【JavaScript】LeetCode:21-25

文章目录 21 最大子数组和22 合并区间23 轮转数组24 除自身以外数组的乘积25 缺失的第一个正数 21 最大子数组和 贪心 / 动态规划贪心:连续和(count)< 0时,放弃当前起点的连续和,将下一个数作为新起点,这里提供使用贪心算法解决本题的代码。动态规划:dp[i]:以nums[i]为结尾的最长连续子序列(子数组)和。 dp[i] = max(dp[i - 1]

2025年25届计算机毕业设计:如何实现高校实验室Java SpringBoot教学管理系统

✍✍计算机毕业编程指导师** ⭐⭐个人介绍:自己非常喜欢研究技术问题!专业做Java、Python、微信小程序、安卓、大数据、爬虫、Golang、大屏等实战项目。 ⛽⛽实战项目:有源码或者技术上的问题欢迎在评论区一起讨论交流! ⚡⚡ Java、Python、微信小程序、大数据实战项目集 ⚡⚡文末获取源码 文章目录 ⚡⚡文末获取源码高校实验室教学管理系统-研究背景高校实验室教学管理系

智力题:25匹马5条跑道找最快的3匹马,最少需要跑几次?

要找出25匹马中最快的3匹马,使用5条跑道,最少需要跑几次?我们可以通过逐步推理来解决这个问题。 第一步:分组比赛 首先,我们将25匹马分成5组,每组5匹马。每组进行一次比赛,这样我们就有5次比赛的结果。 组1:A1, A2, A3, A4, A5 组2:B1, B2, B3, B4, B5 组3:C1, C2, C3, C4, C5 组4:D1, D2, D3, D4, D5 组

芬兰手游业25年发展史

自2010年Rovio凭借《愤怒的小鸟》成功以来,芬兰的优秀开发者可以说是不断的引领手游潮流,有Frogmid、Seriously这样的小型团队,也有Supercell这样的世界收入冠军。除却收入之外,我们可以发现芬兰开发商的手游绝大多数都是具有独特创意的。 为什么芬兰手游业可以具有如此之大的竞争优势?其他人想要赶上应该怎么做?这个答案从来都不是能够简单作答的,因为它根植于芬兰的行业发展史,所以

图形API学习工程(25):实现法线贴图

工程GIT地址:https://gitee.com/yaksue/yaksue-graphics 目标 在《图形API学习工程(10):基础光照》中,我实现了最基础的光照,同时也表现了法线的作用。 在《图形API学习工程(11):使用纹理》中,工程已经能够加载纹理贴图。 这样,法线贴图 所需的准备已经完成,可以在工程里实现这个技术了。 (关于法线贴图的意义,可见上一篇博客《从“法线贴图的意义

【简历】25届南京某一本JAVA简历:简历通过率还好,但是拿不到OFFER

注:为保证用户信息安全,姓名和学校等信息已经进行同层次变更,内容部分细节也进行了部分隐藏 简历说明 今天看一份25届南京某一本大学的Java简历。 这个简历呢,学校是一本。我们说上来先要定校招层次,这个层次就按照中厂来讲。因为现在很多的双非一本目标都是在中厂。 这个同学有个实习经历,一本有八成的同学主项目都是重复的。HR他只能看到项目重不重复,要点对不对他不知道,就从这个角度来看,这位同学

GNU的伪操作 (25)

这里主要是 对 GNU的 各个伪操作进行 详细的解释。 先来看着几个 伪操作。 .byte,  .short,  .long,  .quad , .float ,  这个是关于 字节的。 .string   .ascii 是关于字符串的。 这个字符串编译器是可以自动在末尾补0 的。 举例: val:         .word 0x11223344         m

25版王道数据结构课后习题详细分析 第八章 8.2 插入排序

一、单项选择题 ———————————————————— ———————————————————— 解析:直接插入排序在最坏的情况下要做n(n-1)/2次关键字的比较,当n=5时, 关键字的比较次数为10。注意不考虑与哨兵的比较。 正确答案: ———————————————————— ———————————————————— 解析:由于序列初始基本有序,因此使用直接插入排序

游卡,三七互娱,得物,顺丰,快手,oppo,康冠科技,途游游戏,埃科光电25秋招内推

游卡,三七互娱,得物,顺丰,快手,oppo,康冠科技,途游游戏,埃科光电25秋招内推 ①顺丰 【招聘岗位】研发、算法、大数据、产品、项管、设计、人资等 【官方内推码】4FOLXH 【一键内推】https://sourl.cn/UzbDat ②游卡 【岗位】程序技术、产品策划、美术、发型运营、职能综合、桌游业务等大类 【一键内推】https://sourl.cn/PHiZZE 【内推码】DSymt

(175)时序收敛--->(25)时序收敛二五

1 目录 (a)FPGA简介 (b)Verilog简介 (c)时钟简介 (d)时序收敛二五 (e)结束 1 FPGA简介 (a)FPGA(Field Programmable Gate Array)是在PAL (可编程阵列逻辑)、GAL(通用阵列逻辑)等可编程器件的基础上进一步发展的产物。它是作为专用集成电路(ASIC)领域中的一种半定制电路而出现的,既解决了定制电路的不足,又克服了