PAT-A 真题 – 1154 Vertex Coloring

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 $1 0^{4}$ ), 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$ ( $\leq$ 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 11
8 7
6 8
4 5
8 4
8 1
1 2
1 4
9 8
9 1
1 0
2 4
4
0 1 0 1 4 1 0 1 3 0
0 1 0 1 4 1 0 1 0 0
8 1 0 1 4 1 0 5 3 0
1 2 3 4 5 6 7 8 8 9

Sample Output:

4-coloring
No
6-coloring
No

题目大意：给定一个无向图，然后给出每个点的颜色（使用数字表示）判断是否相邻两个点的颜色不同，如果是，输出整个图使用了多少种颜色，如果不是，输出No

这道题不需要邻接表或者邻接矩阵，直接把边存储了，然后对于每个check，遍历一遍所有的边，判断边的端点颜色是否相同即可。

#include <bits/stdc++.h>
using namespace std;

int H(int a, int b){
  if(a > b) swap(a, b);
  return a * 10000 + b;
}

int main(){
  vector<int> edge;
  int ecnt, vcnt;
  scanf("%d %d", &vcnt, &ecnt);
  for(int i = 0; i < ecnt; i++){
    int a, b;
    scanf("%d %d", &a, &b);
    edge.push_back(H(a, b));
  }
  int qcnt;
  scanf("%d", &qcnt);
  while(qcnt--){
    vector<int> V(vcnt, -1);
    int ccnt = 0;
    unordered_map<int, bool> exist;
    for(int & i : V){
      int tmp;
      scanf("%d", &tmp);
      if(exist[tmp] == false)
        ccnt++;
      exist[tmp] = true;
      i = tmp;
    }
    bool flag = true;
    for(int vtx : edge){
      int start = vtx % 10000, end = vtx / 10000;
      if(V[start] == V[end]) flag = false;
    }
    if(flag) printf("%d-coloring\n", ccnt);
    else printf("No\n");
  }
  return 0;
}

斐斐のBlog