A proper vertex coloring is a labeling of the graph's vertices with colors such that no two vertices sharing the same edge have the same color. A coloring using at most k colors is called a (proper) k-coloring.
Now you are supposed to tell if a given coloring is a proper k-coloring.
Input Specification:
Each input file contains one test case. For each case, the first line gives two positive integers N and M (both no more than 104 ), being the total numbers of vertices and edges, respectively. Then M lines follow, each describes an edge by giving the indices (from 0 to N−1) of the two ends of the edge.After the graph, a positive integer K (≤ 100) is given, which is the number of colorings you are supposed to check. Then K lines follow, each contains N colors which are represented by non-negative integers in the range of int. The i-th color is the color of the i-th vertex.
Output Specification:
For each coloring, print in a line k-coloring if it is a proper k-coloring for some positive k, or No if not.Sample Input:
10 118 76 84 58 48 11 21 49 89 11 02 440 1 0 1 4 1 0 1 3 00 1 0 1 4 1 0 1 0 08 1 0 1 4 1 0 5 3 01 2 3 4 5 6 7 8 8 9Sample Output:
4-coloringNo6-coloringNo题目大意:给出一个无向图,并给出每个顶点所对应的颜色,若每个边所对应的两个顶点颜色都不相同,则满足题意
思路分析:用vector把所有的边都存起来,把所有的顶点的颜色用set存储起来(利用set自动去重),枚举所有边,检查是否每条边的两个顶点的颜色不同,若都不同则输出颜色个数,否则输出No
#include#include #include #include using namespace std;struct edge{ int n1; int n2;};int main(){ int n,m,k; scanf("%d %d",&n,&m); vector v(m); for(int i = 0; i < m; i++ ) scanf("%d %d",&v[i].n1,&v[i].n2); scanf("%d",&k); while(k--){ int NodeColor[10009]; //注意需要放在while循环内,每次都需要重新利用 set color; for(int i = 0; i < n; i++){ scanf("%d",&NodeColor[i]); color.insert(NodeColor[i]); } bool flag = true; for(int i = 0; i < m; i++){ if(NodeColor[v[i].n1] == NodeColor[v[i].n2]){ flag = false; break; } } if(flag) printf("%d%s\n",color.size(),"-coloring"); else printf("No\n"); } return 0;}