A1134 Vertex Cover (25分)

一、技术总结

  1. 题意为,给出一个图,是按边给出,给出每条边两边的顶点id号,然后再给出k个顶点集合,要我们依次判断是否每条边的两个顶点至少有一个在集合中,那么则称该顶点集合为Vertex Cover,同时输出Yes,否则输出No。
  2. 使用一个数组存储每条边的顶点信息,用于判断是否每条边的顶点中至少有一个在所给顶点集合中。
  3. 使用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;
}
上一篇:三、SharpGL的功能应用--图形绘制


下一篇:图算法 广度优先和深度优先递归与非递归