題目內(nèi)容

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 分，首先需要讀懂題目。輸入樣例中首先給出的是相連的各個點，也就是各條邊，因此可以繪出如下的圖

然后給出幾組數(shù)據(jù)，讓分別判斷這些點是否滿足題目中的?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，去除重復(fù)覆蓋的點，可以看到，已經(jīng)完全覆蓋了整個樹的所有點，這就是 Vertex Cover。

在代碼實現(xiàn)中，為了方便標注，需要構(gòu)造一個 vert_in_edge 的字典，其含義是給各個邊編號，號碼作為鍵名存儲，鍵值是這個邊的兩個端點。

需要注意的是復(fù)制列表、字典時要用 copy() 函數(shù)，否則只是將引用傳遞給新的變量。

源代碼