PAT-A 真题 – 1134 Vertex Cover

A vertex cover of a graph is a set of vertices such that each edge of the graph is incident to at least one vertex of the set. Now given a graph with several vertex sets, you are supposed to tell if each of them is a vertex cover or not.

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 the 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 queries. Then $K$ lines of queries follow, each in the format:

$N^{v}$ $v [1]$ $v [2] \dots v [N^{v}]$

where $N^{v}$ is the number of vertices in the set, and $v [i]$ 's are the indices of the vertices.

Output Specification:

For each query, print in a line Yes if the set is a vertex cover, 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
5
4 0 3 8 4
6 6 1 7 5 4 9
3 1 8 4
2 2 8
7 9 8 7 6 5 4 2

Sample Output:

No
Yes
Yes
No
No

题目大意：给定一个图，接着给出几个点，判断是不是图中的任意一条边都会途径这个点

这道题可以把每个边设置一个编号，我这里设置边号的策略是，用size_t的前5位表示连成边的两个点的数字中较小的一个，后5位是较大的一个，这样就可以保证每一条边的边号都具有唯一性了。

在存储图时，使用邻接表来存储，在查询时，每输入一个点，标记与这个点所连接的所有边已访问。并将计数器+1

这个映射关系可以用unordered_map<size_t, bool>来存储（直接用map运行时间580ms，有超时的风险）

接着判断最终计数器是否等于总边数（即所有边都访问过，边上的任一点都会途径给定的点集）

代码：

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
const size_t maxn = 10010;
vector<int> G[maxn];  //邻接表 

size_t Hash(int a, int b){
  if(a > b) swap(a, b);  //保证 a<b，两点之间的边的id具有唯一性 
  return a * 100000 + b;
}

int main(){
  int vcnt, ecnt, qcnt;
  scanf("%d %d", &vcnt, &ecnt);
  for(int i = 0; i < ecnt; i++){
    int _l, _r;
    scanf("%d %d", &_l, &_r);
    G[_l].push_back(_r);
    G[_r].push_back(_l);
  }
  scanf("%d", &qcnt);
  for(int i = 0; i < qcnt; i++){  //对于每一个查询 
    unordered_map<size_t, bool> H;
    int K, __cnt = 0;
    scanf("%d", &K);
    for(int j = 0; j < K; j++){  //读入要查询的所有点 
      int v;
      scanf("%d", &v);
      for(auto it : G[v]){  //遍历与该点连接的所有边
        size_t _hash = Hash(v, it);  //获取这个边的id 
        if(H[_hash] == 0){  //边没访问过
          __cnt++;  //计数器++ 
          H[_hash] = 1;  //标记已访问 
        }
      }
    }
    if(__cnt == ecnt) printf("Yes\n");
    else printf("No\n");
  } 
  return 0;
}

斐斐のBlog