图着色问题是一个著名的NP完全问题。给定无向图 G = (V, E)，问可否用K种颜色为V中的每一个顶点分配一种颜色，使得不会有两个相邻顶点具有同一种颜色？ 但本题并不是要你解决这个着色问题，而是对给定的一种颜色分配，请你判断这是否是图着色问题的一个解。
输入格式：
输入在第一行给出3个整数V（0 < V <= 500）、E（>= 0）和K（0 < K <= V），分别是无向图的顶点数、边数、以及颜色数。顶点和颜色都从1到V编号。随后E行，每行给出一条边的两个端点的编号。在图的信息给出之后，给出了一个正整数N（<= 20），是待检查的颜色分配方案的个数。随后N行，每行顺次给出V个顶点的颜色（第i个数字表示第i个顶点的颜色），数字间以空格分隔。题目保证给定的无向图是合法的（即不存在自回路和重边）。
输出格式：
对每种颜色分配方案，如果是图着色问题的一个解则输出“Yes”，否则输出“No”，每句占一行。
输入样例：
6 8 3
2 1
1 3
4 6
2 5
2 4
5 4
5 6
3 6
4
1 2 3 3 1 2
4 5 6 6 4 5
1 2 3 4 5 6
2 3 4 2 3 4
输出样例：
Yes
Yes
No
No
用邻接表表示图，每个顶点的邻接点可以很容易找到，这样就可以判断他们两个的颜色是否是一样。另一个问题时给出的颜色的个数必须是K个，多了少了都不行。 verify函数是验证图中的相邻顶点是否存在相同的颜色，即对颜色的判断。 color_num函数是有多少个不同的颜色个数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
| #include <cstdio>
#include <vector>
#include <cstdlib>
using namespace std;
bool verify(vector<vector<int>> vertex, int *color, int v) {
for (int i = 1; i <= v; i++) {
for (int j = 0; j < vertex[i].size(); j++) {
if (color[vertex[i][j]] == color[i]) {
return false;
}
}
}
return true;
}
int color_num(int *color, int v) {
color[0] = -1;
qsort(color, v + 1, sizeof(*color), [](const void *a, const void *b) {
int arg1 = *static_cast<const int *>(a);
int arg2 = *static_cast<const int *>(b);
if (arg1 < arg2) return -1;
if (arg1 > arg2) return 1;
return 0;
});
int i = 1, j = 2;
while (j <= v) {
if (color[j] != color[i]) color[++i] = color[j];
j++;
}
return i;
}
int main() {
int v = 0, e = 0, k = 0, v1 = 0, v2 = 0, n = 0;
scanf("%d %d %d", &v, &e, &k);
vector<vector<int> > vertex(v + 1);
for (int i = 0; i < e; i++) {
scanf("%d %d", &v1, &v2);
vertex[v1].push_back(v2);
vertex[v2].push_back(v1);
}
scanf("%d", &n);
for (int i = 0; i < n; i++) {
int *color = new int[v + 1];
for (int j = 1; j <= v; j++) scanf("%d", &color[j]);
if (verify(vertex, color, v) && color_num(color, v) == k) printf("Yes\n");
else printf("No\n");
delete[] color;
}
return 0;
}
|