7-2 图着色问题

输入样例：

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

idea

注意合理的方案需满足：用到的颜色数== 给定颜色数

solution

#include 
#include 
#include 
using namespace std;
int arcs[500][500];

int main(){
	int n, e, k, v1, v2, m, count, flag, p[500], t[500];
	memset(arcs, 0, sizeof(arcs));
	scanf("%d%d%d", &n, &e, &k);
	for(int i = 0; i < e; i++){
		scanf("%d%d", &v1, &v2);
		arcs[v1-1][v2-1] = arcs[v2-1][v1-1] = 1;
	}
	scanf("%d", &m);
	while(m--){
		count = 1;
		flag = 1;
		for(int i = 0; i < n; i++){
			scanf("%d", p + i);
			t[i] = p[i];
		}
		sort(p, p + n);
		for(int i = 1; i < n; i++){
			if(p[i] != p[i - 1]) count ++;
		}
		if(count != k) flag = 0;
		else{
			for(int i = 0; i < n; i++){
				for(int j = 0; j < n; j++){
					if(arcs[i][j] == 1 && t[i] == t[j])  flag = 0;
				}
			}
		}
		if(flag) printf("Yes\n");
		else printf("No\n");
	}
	return 0;
}
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