博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
1154 Vertex Coloring (25 分)
阅读量:5813 次
发布时间:2019-06-18

本文共 2066 字,大约阅读时间需要 6 分钟。

A proper vertex coloring is a labeling of the graph's vertices with colors such that no two vertices sharing the same edge have the same color. A coloring using at most k colors is called a (proper) k-coloring.

Now you are supposed to tell if a given coloring is a proper k-coloring.

Input Specification:

Each input file contains one test case. For each case, the first line gives two positive integers N and M (both no more than 10
​4
​​ ), being the total numbers of vertices and edges, respectively. Then M lines follow, each describes an edge by giving the indices (from 0 to N−1) of the two ends of the edge.

After the graph, a positive integer K (≤ 100) is given, which is the number of colorings you are supposed to check. Then K lines follow, each contains N colors which are represented by non-negative integers in the range of int. The i-th color is the color of the i-th vertex.

Output Specification:

For each coloring, print in a line k-coloring if it is a proper k-coloring for some positive k, or No if not.


Sample Input:

10 11
8 7
6 8
4 5
8 4
8 1
1 2
1 4
9 8
9 1
1 0
2 4
4
0 1 0 1 4 1 0 1 3 0
0 1 0 1 4 1 0 1 0 0
8 1 0 1 4 1 0 5 3 0
1 2 3 4 5 6 7 8 8 9


Sample Output:

4-coloring
No
6-coloring
No


题目大意:给出一个无向图,并给出每个顶点所对应的颜色,若每个边所对应的两个顶点颜色都不相同,则满足题意

思路分析:用vector把所有的边都存起来,把所有的顶点的颜色用set存储起来(利用set自动去重),枚举所有边,检查是否每条边的两个顶点的颜色不同,若都不同则输出颜色个数,否则输出No


#include 
#include
#include
#include
using namespace std;struct edge{ int n1; int n2;};int main(){ int n,m,k; scanf("%d %d",&n,&m); vector
v(m); for(int i = 0; i < m; i++ ) scanf("%d %d",&v[i].n1,&v[i].n2); scanf("%d",&k); while(k--){ int NodeColor[10009]; //注意需要放在while循环内,每次都需要重新利用 set
color; for(int i = 0; i < n; i++){ scanf("%d",&NodeColor[i]); color.insert(NodeColor[i]); } bool flag = true; for(int i = 0; i < m; i++){ if(NodeColor[v[i].n1] == NodeColor[v[i].n2]){ flag = false; break; } } if(flag) printf("%d%s\n",color.size(),"-coloring"); else printf("No\n"); } return 0;}

转载地址:http://mojbx.baihongyu.com/

你可能感兴趣的文章
post提交返回json格式
查看>>
Java.lang 包中的Void类型
查看>>
正确理解linux grep 的姿势
查看>>
Nhibernate 使用 (一)
查看>>
【转】Android APK的数字签名的作用和意义
查看>>
C++ Primer 有感(标准库map类型)
查看>>
(23)Spring Boot启动加载数据CommandLineRunner【从零开始学Spring Boot】
查看>>
Android ImageView加载圆形图片且同时绘制圆形图片的外部边缘边线及边框
查看>>
链表的反转
查看>>
动态从数据库获取数据(Vue.js)【数据可变】
查看>>
操作linux命令
查看>>
转载]typedef struct和struct的区别
查看>>
数据仓库、数据整合、ETL、ELT和EII之间的区别?
查看>>
c++ 注册表操作dll动态调用
查看>>
C#开发人员应该知道的13件事情
查看>>
工厂模式(Factory)
查看>>
Linux 虚拟地址与物理地址的映射关系分析【转】
查看>>
GNU make manual 翻译(三十七)
查看>>
自动化测试框架的搭建
查看>>
Linux 邮件服务器 之跟我一步一步来实现一个邮件系统【转】
查看>>