PAT(Advanced)1154 Vertex Coloring (25 分)

1154 Vertex Coloring (25 分)

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$ ($\le$ 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

题目解读：顶点着色题，规定在同一条边上的两个顶点不可以着同一颜色，先输入顶点数、边数，输入边的顶点，接着输入k次测试条件，每一行表示每次测试每个顶点的着色情况。如果满足条件则输出是几色着色图形，若不满足则输出“No”

解题思路： 比较简单的遍历图的题，用边来存储图，另开一个颜色的数组来记录颜色的情况，用set来数有多少个颜色会比较方便，没什么坑的好题QWQ！！

AC代码

#include <iostream>
#include <vector>
#include <memory>
#include <set>
using namespace std;
struct edge {
	int v;
	int u;
	edge(int _v, int _u) {
		v = _v;
		u = _u;
	}
};
vector<edge> graph;
int color[10004];
int n, m;
set<int> colorset;
int main()
{
	scanf("%d %d", &n, &m);
	for (int i = 0; i < m; i++) {
		int a, b;
		scanf("%d %d", &a, &b);
		graph.push_back(edge(a,b));
	}
	int k;
	scanf("%d", &k);
	for (int i = 0; i < k; i++) {
		int flag = 1;
		colorset.clear();
		fill(color, color + 10004, -1);
		for (int i = 0; i < n; i++) {
			scanf("%d", &color[i]);
			colorset.insert(color[i]);
		}
		for (auto edg : graph) {
			if (color[edg.u] == color[edg.v]) {
				flag = 0;
			}
		}
		if (flag)
			printf("%d-coloring\n", colorset.size());
		else {
			printf("No\n");
		}
	}
}