万网x3主机l系统放两个网站,自学设计的网站,原创文字的网站,东莞企业网站定制设计图着色问题是一个著名的NP完全问题。给定无向图G(V,E)#xff0c;问可否用K种颜色为V中的每一个顶点分配一种颜色#xff0c;使得不会有两个相邻顶点具有同一种颜色#xff1f; 但本题并不是要你解决这个着色问题#xff0c;而是对给定的一种颜色分配#xff0c;请你判断这…图着色问题是一个著名的NP完全问题。给定无向图G(V,E)问可否用K种颜色为V中的每一个顶点分配一种颜色使得不会有两个相邻顶点具有同一种颜色 但本题并不是要你解决这个着色问题而是对给定的一种颜色分配请你判断这是否是图着色问题的一个解。
输入格式 输入在第一行给出3个整数V0V≤500、E≥0和K0K≤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 1.根据题目的解析我们不难发现如果颜色的数量不等于k的话直接是No的。 2.如果遇到有相同的颜色就判断是否在同一个边如果在的话就是No
所以我们的解题思路就是 1.用一个二位数组来构建无向图。 2.再用一个二维数组来计入对应颜色的节点这里题目给出了颜色的顺序是1-v的所以可以用二维数组的横向来代表每一种颜色二里面的值就是存放的节点如果发现size() 0了说明遇到相同的颜色了就需要判断这两个节点是否有公共的边。
代码实现
using namespace std;
#include vector
#include unordered_setint 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;vectorint r[510];//存入对应颜色的节点while (n--){unordered_setint 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;
}
