PAT 1134. Vertex Cover (25)

Posted on Edited on In

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 104), 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: Nv v[1] v[2] … v[Nv] 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:

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

结点覆盖的意思是，给一组顶点，判断这组定点能否访问到图中所有的边。 对每一组给出的顶点，对一组定点中的每一个顶点访问它的邻接点，计算访问过的次数，同时把这个顶点标记为已经访问过的，最后得到的访问边的次数不等于题目的m，就是表示没有访问到所有的边。 用邻接矩阵会超内存，用邻接表处理也更方便一些。 代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

vector<vector<int>> vertex;

int bfs(vector<int> v, int n) {
    bool *visit = new bool[n];
    fill(visit, visit + n, false);
    int cnt = 0;
    for (int i = 0; i < v.size(); i++) {
        vector<int> list = vertex[v[i]];
        visit[v[i]] = true;
        for (int j = 0; j < list.size(); j++) {
            if (!visit[list[j]]) {
                cnt++;
            }
        }
    }
    return cnt;
}

int main() {
    int n = 0, m = 0, a = 0, b = 0, k = 0;
    scanf("%d %d", &n, &m);
    vertex.resize(n);
    for (int i = 0; i < m; i++) {
        scanf("%d %d", &a, &b);
        vertex[a].push_back(b);
        vertex[b].push_back(a);
    }
    scanf("%d", &k);
    for (int i = 0; i < k; i++) {
        int nv = 0;
        scanf("%d", &nv);
        vector<int> v(nv);
        for (int j = 0; j < nv; j++) {
            scanf("%d", &v[j]);
        }
        if (bfs(v, n) == m) {
            printf("Yes\n");
        } else {
            printf("No\n");
        }
    }
    return 0;
}