PAT甲级1142Maximal Clique

Posted on | | Visitors:
Words count in article: 733 字 | Reading time ≈ 3 分

题目链接

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

题解

题目要求

  • 团：某无向图的一个顶点子集，其中任意两个不同的顶点相邻，则这个顶点子集是这个图的一个团。
  • 极大团：如果一个团在加入任何一个顶点后都不再是一个团，则这个团是一个极大团。

现在给你一个图，请你判断一些点集是否是团或极大团。

  • 输入

    • Nv：正整数，不超过200，图中顶点的数量
    • Ne：正整数，图中边的数量
    • Ne条边：顶点索引为[1,Nv]
    • M：正整数，不超过100，需要判断的顶点子集的个数
    • M个顶点子集：第一个数字k是顶点个数（不超过Nv），剩下的数字是顶点索引

  • 输出

    对于每个顶点子集，请判断它是最大团还是最大团以外的团或者不是团

思路

  1. 使用邻接矩阵保存边，用二维数组表示

  2. 使用vector保存顶点子集，并使用set保存顶点子集以外的顶点

  3. 根据定义判断顶点子集中的顶点是否两两相邻，如果是则为团，不是则不是团

  4. 如果是团，根据最大团的定义，遍历顶点子集以外的顶点，判断是否可以再添加一个顶点且该顶点与顶点子集中每个顶点都相邻

    如果可以则说明不是极大团，不可以则不是极大团

代码

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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
// Problem: PAT Advanced 1142
// URL: https://pintia.cn/problem-sets/994805342720868352/problems/994805343979159552
// Tags: Graph Clique Maximal Clique

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

bool edge[201][201];

int main()
{
    int ne, nv, m;
    scanf("%d %d", &nv, &ne);

    int v1, v2;
    for (int i = 0; i < ne; i++){ // 记录边
        scanf("%d %d", &v1, &v2);
        edge[v1][v2] = edge[v2][v1] = true;
    }

    scanf("%d", &m);
    while (m--){ // 判断m个顶点子集
        set<int> leftV; // 该顶点子集以外的结点
        for (int i = 1; i <= nv; i++){
            leftV.insert(i);
        }
        int k;
        scanf("%d", &k);
        vector<int> v(k);
        for (int i = 0; i < k; i++){ // 记录顶点子集
            scanf("%d", &v[i]);
            leftV.erase(v[i]);
        }

        bool isClique = true; // 先判断是否是团
        for (int i = 0; i < k - 1; i++){
            for (int j = i + 1; j < k; j++){
                if (edge[v[i]][v[j]] == false){
                    isClique = false;
                    break;
                }
            }
            if (isClique == false)
                break;
        }

        if (isClique == false){
            printf("Not a Clique\n");
            continue;
        }

        bool isMaximalClique = true; // 如果是团，再判断是不是极大团（按照定义判断）
        for (auto it = leftV.begin(); it != leftV.end(); it++){
            int cnt = 0;
            for (int i = 0; i < k; i++){
                if (edge[*it][v[i]] == true)
                    cnt++;
            }
            if (cnt == k){
                isMaximalClique = false;
                break;
            }
        }

        if (isMaximalClique) printf("Yes\n");
        else printf("Not Maximal\n");
    }
    return 0;
}

作者：@臭咸鱼

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

欢迎讨论和交流!