题目内容

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⁴), being the total numbers of vertices and the edges, respectively. Then 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: 

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:

Sample Output:

题目要点

本题 25 分，首先需要读懂题目。输入样例中首先给出的是相连的各个点，也就是各条边，因此可以绘出如下的图

然后给出几组数据，让分别判断这些点是否满足题目中的 Vertex Cover。从字面意义上理解，Cover就是覆盖的含义。对于给定集合的每个点来说，如果点的各个边，或者说相邻的点都被纳入、覆盖，那么给出的集合就是 Vertex Cover。

如图所示，1有4个边，分别是<1,0> <1,2> <1,8> <1,9>，那么1、0、2、8、9这些点就被覆盖。对于8来说有5个边，分别是<8,1> <8,4> <8,6> <8,7> <8,9>，那么8、1、4、6、7这些点也被覆盖。对于4来说有3个边，分别是<4,2> <4,5> <4,8>，那么4、2、5、8这些点也被覆盖。

将所有覆盖的点合计，1、0、2、8、9、8、1、4、6、7、4、2、5、8，去除重复覆盖的点，可以看到，已经完全覆盖了整个树的所有点，这就是 Vertex Cover。

在代码实现中，为了方便标注，需要构造一个 vert_in_edge 的字典，其含义是给各个边编号，号码作为键名存储，键值是这个边的两个端点。

需要注意的是复制列表、字典时要用 copy() 函数，否则只是将引用传递给新的变量。

源代码