# PAT(A) 1134. Vertex Cover (25)

### 1134. Vertex Cover (25)

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 104), 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 (<= 100) is given, which is the number of queries. Then K lines of queries follow, each in the format:

Nv v v ... v[Nv]

where Nv 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

### 代码

  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 48 49 50 51 52 53 /* * Problem: 1134. Vertex Cover (25) * Author: HQ * Time: 2018-03-13 * State: Done * Memo: set */ #include "iostream" #include "set" #include "vector" using namespace std; struct Node { int b; int e; }; int N, M, K; set v; vector edges; int main() { scanf("%d %d",&N, &M); int x,y; for (int i = 0; i < M; i++) { scanf("%d %d", &x, &y); struct Node temp = { x,y }; edges.push_back(temp); } int n; scanf("%d", &K); for (int i = 0; i < K; i++) { scanf("%d", &n); v.clear(); for (int j = 0; j < n; j++) { scanf("%d", &x); v.insert(x); } bool flag = true; for (int j = 0; j < M; j++) { if (v.find(edges[j].b) == v.end() && v.find(edges[j].e) == v.end()) { flag = false; break; } } if (flag) cout << "Yes" << endl; else cout << "No" << endl; } system("pause"); }