17年春季第三题 PAT甲级 1134 Vertex Cover (25分)

痛定思痛。 2023-07-18 02:59 6阅读 0赞

题目来源：[https://pintia.cn/problem-sets/994805342720868352/problems/994805346428633088][https_pintia.cn_problem-sets_994805342720868352_problems_994805346428633088]

备考汇总贴：[2020年6月PAT甲级满分必备刷题技巧][2020_6_PAT]

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

Nv v\[1\] v\[2\]⋯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

# 题目大意 #

**给n个结点m条边，再给k个集合。对这k个集合逐个进行判断。每个集合S里面的数字都是结点编号，求问整个图是否符合顶点覆盖的定义（即所有的m条边两端的结点，是否至少一个结点出自集合S中）。如果是，输出Yes否则输出No。**

# 题目分析 #

用vector和结构体存边，然后遍历每条边，如果存在一条边，它的两个顶点都不在查询的集合里，那就输出No，否则输出Yes。

# 满分代码 #

#include<iostream>
    #include<vector>
    using namespace std;
    struct edge{
        int a,b;
    };
    int main(){
        int n,m,k,e,x;
        scanf("%d %d",&n,&m);
        vector<edge> g(m);
        for(int i=0;i<m;i++){
            scanf("%d %d",&g[i].a,&g[i].b);
        }
        cin>>k;
        while(k--){
            cin>>e;
            set<int> s;
            for(int j=0;j<e;j++){
                scanf("%d",&x);
                s.insert(x);
            }
            bool f=true;
            for(int i=0;i<m;i++){
                if(s.find(g[i].a)==s.end()&&s.find(g[i].b)==s.end()){
                    cout<<"No"<<endl;
                    f=false;
                    break;
                }
            }
            if(f)cout<<"Yes"<<endl;
        }
    }

[https_pintia.cn_problem-sets_994805342720868352_problems_994805346428633088]: https://pintia.cn/problem-sets/994805342720868352/problems/994805346428633088
[2020_6_PAT]: https://blog.csdn.net/allisonshing/article/details/104213959