一、技术总结
- 题意为,给出一个图,是按边给出,给出每条边两边的顶点id号,然后再给出k个顶点集合,要我们依次判断是否每条边的两个顶点至少有一个在集合中,那么则称该顶点集合为Vertex Cover,同时输出Yes,否则输出No。
- 使用一个数组存储每条边的顶点信息,用于判断是否每条边的顶点中至少有一个在所给顶点集合中。
- 使用set容器来存储所给的顶点号,因为可以方便的使用find函数进行查找信息。那么进行判断即可,一旦出现某一条边中有顶点不在集合中,输出No,并且停止遍历。
二、参考代码
#include<iostream>
#include<set>
using namespace std;
struct node{
int id1, id2;
};
int main(){
int n, m, k;
scanf("%d%d", &n, &m);
node edge[10010];
for(int i = 0; i < m; i++){
scanf("%d%d", &edge[i].id1, &edge[i].id2);
}
scanf("%d", &k);
for(int i = 0; i < k; i++){
int num, v;
set<int> temp;
scanf("%d", &num);
for(int j = 0; j < num; j++){
scanf("%d", &v);
temp.insert(v);
}
int flag = true;
for(int j = 0; j < m; j++){
if(temp.find(edge[j].id1) == temp.end() &&
temp.find(edge[j].id2) == temp.end()){
printf("No\n");
flag = false;
break;
}
}
if(flag) printf("Yes\n");
}
return 0;
}