L2-023. 图着色问题
参考博客
1 #include <iostream>
2 #include <cstring>
3 #include <set>
4
5 using namespace std;
6
7 int v, e, k;
8 int map[501][501] = {0};
9 int color[501] = {0};
10
11 bool flag = true;
12 bool vis[501];
13
14 void isYes(int i) {
15 if (vis[i] || flag == false) {
16 return;
17 }
18 vis[i] = true;
19 for (int j = 0; j < v; j++) {
20 if (color[i] == color[j] && map[i][j] == 1) {
21 flag = false;
22 return;
23 } else if (map[i][j] == 1 && vis[j] == false){
24 isYes(j);
25 }
26 }
27 }
28
29 int main()
30 {
31 cin >> v >> e >> k;
32 for (int i = 0; i < e; i++) {
33 int x, y;
34 cin >> x >> y;
35 x--;
36 y--;
37 map[x][y] = 1;
38 map[y][x] = 1;
39 }
40 int m;
41 cin >> m;
42 for (int i = 0; i < m; i++) {
43 set<int> s;
44 for (int j = 0; j < v; j++) {
45 int c;
46 cin >> c;
47 s.insert(c);
48 color[j] = c;
49 }
50 if (s.size() != k) {
51 flag = false;
52 } else {
53 memset(vis, false, sizeof(vis));
54 flag = true;
55 for (int j = 0; j < v; j++) {
56 isYes(j);
57 if (flag == false) {
58 break;
59 }
60 }
61 }
62 if (flag) {
63 cout << "Yes" << endl;
64 } else {
65 cout << "No" << endl;
66 }
67 }
68 return 0;
69 }