题目粗心:

如果一个图的所有边的领接点至多有一个点在汇合中,那么就称为这个汇合为一个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;}