L2-3 图着色问题

图着色问题是一个著名的NP完全问题。给定无向图G=(V,E)，问可否用K种颜色为V中的每一个顶点分配一种颜色，使得不会有两个相邻顶点具有同一种颜色？
但本题并不是要你解决这个着色问题，而是对给定的一种颜色分配，请你判断这是否是图着色问题的一个解。

输入格式：
输入在第一行给出3个整数V（0

输出格式：
对每种颜色分配方案，如果是图着色问题的一个解则输出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

1.根据题目的解析，我们不难发现，如果颜色的数量不等于k的话直接是No的。
2.如果遇到有相同的颜色，就判断是否在同一个边，如果在的话就是No

所以我们的解题思路就是
1.用一个二位数组来构建无向图。
2.再用一个二维数组来计入对应颜色的节点，这里题目给出了颜色的顺序是1-v的，所以可以用二维数组的横向来代表每一种颜色二里面的值就是存放的节点，如果发现size() > 0了说明遇到相同的颜色了，就需要判断这两个节点是否有公共的边。

代码实现：

using namespace std;
#include 
#include 

int arr[510][510];
int main()
{
	int v, e, k;
	cin >> v >> e >> k;
	//构建无向图
	while (e--)
	{
		int a, b; cin >> a >> b;
		arr[a][b] = 1;
		arr[b][a] = 1;
	}

	int n; cin >> n;
	int flag = 0;
	int cr = 0;
	vector r[510];//存入对应颜色的节点
	while (n--)
	{
		unordered_set st;//记录颜色的个数
		for (int i = 1; i <= v; i++)
		{
			cin >> cr;
			st.insert(cr);
			//如果出现重复的颜色，就进行判断
			if (r[cr].size() > 0) //出现了相同的颜色
			{
				//判断具有相同颜色的节点是否与当前节点有共同的边
				for (int j = 0; j < r[cr].size(); j++)
				{
					if (arr[i][r[cr][j]]) 
						flag = 1;
				}
			}
			if (flag) break;
			r[cr].push_back(i);
		}
		if (st.size() != k) flag = 1;
		if (flag == 1) printf("No\n");
		else printf("Yes\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
40
41
42
43
44
45
46
47