关于算法-数据结构:PAT甲级1134-Vertex-Cover

题目粗心：

如果一个图的所有边的领接点至多有一个点在汇合中，那么就称为这个汇合为一个 vertex cover，现给出一个图的顶点 N 和边数 M，M 条边的信息, 和 K 次查问的汇合元素，问以后汇合是否是该图的一个 vertex cover。

算法思路：

咱们应用 edges 数组存储输出的 M 条边，每一次查问的时候就应用 unordered_map<int,bool> vertices 记录输出的汇合顶点为 true，而后遍历每一条边，如果该边的 2 个领接点有一个不存在汇合中，输入 No，否则输入 Yes。

提交后果：

AC 代码:

#include<cstdio>
#include <unordered_map>

using namespace std;

struct Edge{int a,b;}edges[10005];

int main(){
    int N,M;
    scanf("%d %d",&N,&M);
    for (int i = 0; i < M; ++i) {
        int a,b;
        scanf("%d %d",&a,&b);
        edges[i].a = a;
        edges[i].b = b;
    }
    int K;
    scanf("%d",&K);
    for (int j = 0; j < K; ++j) {
        unordered_map<int,bool> vertices;
        scanf("%d",&N);
        for (int i = 0; i < N; ++i) {
            int vertex;
            scanf("%d",&vertex);
            vertices[vertex] = true;
        }
        bool isCover = true;
        for(int i=0;i<M;++i){if(!vertices[edges[i].a]&&!vertices[edges[i].b]){
                // 该边的 2 个顶点都没有呈现在汇合中
                isCover = false;
                break;
            }
        }
        if(isCover){printf("Yes\n");
        } else {printf("No\n");

        }
    }
    return 0;
}