PAT甲级1134Vertex Cover

Posted on | | Visitors:
Words count in article: 793 字 | Reading time ≈ 4 分

题目链接

https://pintia.cn/problem-sets/994805342720868352/problems/994805346428633088

题目要求

  • vertex cover

    vertex cover指图中的每条边都和这组顶点中至少一个顶点相关，先给定一个图和几组顶点，请判断这几组顶点是否为vertex cover

  • 输入

    • N：顶点数量，不超过10000

    • M：边的数量，不超过10000

    • M条边：顶点通过[0,N-1]表示/索引

    • K：有几组顶点，不超过100

    • K组顶点

      一组顶点的第一个数字是顶点数量，剩下的是顶点索引

  • 输出

    • 是vertex则输出Yes，不是则输出No

题解一

思路

  • 定义Edge结构体，包括两个端点

  • 把M条边存入vector

  • 将顶点组存入set（vector也可以）

  • 遍历每条边判断其两个端点是否在set中

    只要有一条边的两个端点都不在set中，则不是vertex cover

代码

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
// Problem: PAT Advanced 1134
// URL: https://pintia.cn/problem-sets/994805342720868352/problems/994805346428633088
// Tags: Graph Hash Set

#include <iostream>
#include <set>
#include <vector>
using namespace std;

struct Edge{
    int v1, v2;
};

int main()
{
    int n, m, k;
    scanf("%d %d", &n, &m);
    
    vector<Edge> edges(m); // 存储边
    for (int i = 0; i < m; i++)
        scanf("%d %d", &edges[i].v1, &edges[i].v2);

    scanf("%d", &k);
    while (k--){
        set<int> vertices;
        int vertexNum, vertex;
        scanf("%d", &vertexNum);
        for (int i = 0; i < vertexNum; i++){ // 将一组顶点存入set
            scanf("%d", &vertex);
            vertices.insert(vertex);
        }

        bool isVertexCover = true;
        for (auto it = edges.begin(); it != edges.end(); it++){
            // 只要有一条边的两个端点都不在set中，则不是vertex cover
            if (vertices.find(it->v1) == vertices.end() && vertices.find(it->v2) == vertices.end()){
                isVertexCover = false;
                break;
            }
        }
        if (isVertexCover)
            printf("Yes\n");
        else
            printf("No\n");
    }
    return 0;
}

题解二

比上一个方法快

思路

  • 给M条边编号为[0,M-1]
  • 读取每条边时，保存每个顶点与哪条边相关，将这个信息存入vector
  • 定义vector表示各条边是否被覆盖，遍历上一步得到的vector标记各条边是否被覆盖，最后遍历这一步定义的vector判断是否符合vertex cover的条件

注意点

  • 一个顶点可以和多条边相关

代码

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
// Problem: PAT Advanced 1134
// URL: https://pintia.cn/problem-sets/994805342720868352/problems/994805346428633088
// Tags: Graph Hash Set

#include <iostream>
#include <vector>
using namespace std;

int main()
{
    int n, m, k;
    scanf("%d %d", &n, &m);

    vector<int> cover[n]; // cover[2].push_back(3) 代表顶点2覆盖了边3
    int v1, v2;
    for (int i = 0; i < m; i++){
        scanf("%d %d", &v1, &v2);
        cover[v1].push_back(i);
        cover[v2].push_back(i);
    }

    scanf("%d", &k);
    while (k--){
        vector<bool> isCovered(m, false); // m条边是否被覆盖
        int vertexNum, vertex;
        scanf("%d", &vertexNum);
        for (int i = 0; i < vertexNum; i++){ // 遍历顶点，将其覆盖的边标记
            scanf("%d", &vertex);
            for (int j = 0; j < cover[vertex].size(); j++)
                isCovered[cover[vertex][j]] = true;
        }
        bool isVertexCover = true;
        for (int i = 0; i < m; i++){
            if (isCovered[i] == false){
                isVertexCover = false;
                break;       
            }
        }
        if (isVertexCover)
            printf("Yes\n");
        else
            printf("No\n");        
    }
    return 0;
}

参考链接

https://blog.csdn.net/liuchuo/article/details/78037329

作者：@臭咸鱼

转载请注明出处：https://www.cnblogs.com/chouxianyu/

欢迎讨论和交流!