1154_vertex_coloring

前言

最近开始做pat的题目了，题目感觉和leetcode还是区别比较大的，和蓝桥杯有一定的相似点。主要是对于输入输出的要求比较严格，我所报名的甲级是英文题目，其中部分单词还是不太熟悉，意思只能看靠猜测了，这方面还需要积累。关于语言方面，我觉得pat方面是有点坑的，它对于所有语言的时间要求是一样的，这对于用python（或者说非C++）选手来说很不友好。很简单的题目，用python语言实现和C++一样的算法，总是会有部分用例超时，所以我又被迫捡起了C++。但是好像目前各种机试的语言主要还是C++，也算是提前熟悉一下吧（有一般的报错是格式问题）。pat甲级目前题库一共有150+题目，感觉还是有希望熟悉一遍的（flag），其他的也不多说了，在家虽然没用那么舒服，还是要🐛🐛🐛。

题目

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

单词

Vertex: 顶点

分析

刚读到这个题目，一开始以为是一个图色问题，这方面还是不太熟悉。但是仔细读了一下，发现只需要判断一下就好了。一开始按照我的思路，我是用邻接表来存每条边，最后总是时间超时。参考了一下题解，发现题解直接存储了每条边。。其实这样效率更高，还是我把问题复杂化了。对于算法题来说，其实还是只要能够达到效果即可，不必要一定要复杂化问题。

本题的思路其实还是很简单，根据给出的每条边，对于其两个顶点，判断一下颜色是否相同即可。

代码

#include
#include
#include

using namespace std;

struct node{ //存储边
    int x, y;
};

int main(){
    int N, M;
    cin >> N >> M; 
    vector v(M); //存储所有的边

    for(int i=0; i s; // 使用set统计颜色数量
        vector a(N); // 存储每种图色方案
        for(int j=0; j