pat 1134 Vertex Cover (25分) 超时问题

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

N?v?? v[1] v[2]?v[N?v??]

where N?v?? 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:

10 11
8 7
6 8
4 5
8 4
8 1
1 2
1 4
9 8
9 1
1 0
2 4
5
4 0 3 8 4
6 6 1 7 5 4 9
3 1 8 4
2 2 8
7 9 8 7 6 5 4 2

Sample Output:

No
Yes
Yes
No
No

这道题目的意思，就是给定一个图，然后K条测试用例，每条测试用例，输入几个点，如果这几个点所连接的边，包含了整个图所有的边，就输出Yes，否则就输出No

这道题目我开始做思路是，是对于每条边，存储它的左端点，存储它的右端点，然后每个测试用例每个点，都去遍历每条边的两个端点，如果左端点或者右端点是这个点，就把这条边加进去，最后看是不是

所有边都加进去了。可惜的是最后两个用例超时了。

于是我换了另外一种存储结构，把每个点连接的边用vector存起来，最后遍历给定的点，看是否包含了所有的边。

#include
#include
#include
#include
#include