1142. Maximal Clique.md

【PAT A-1142】Maximal Clique

题意概述

在一个无向图中，如果在给定的顶点集中任意两个不同的点之间都有一条边，那么我们称这样的点集为 Clique。如果一个 clique 点集不可以再加入任何一个新的结点构成新的 clique，我们称这样的 Clique 为 Maximal Clique。给定一个无向图和 M 个查询，问对于每一个查询中的点集是否是 Maximal Clique，如果不是，是否是 Clique。

输入输出格式

输入第一行包含 2 个正整数 N 和 M，分别表示无向图的顶点个数和边的个数。接下来 M 行，每行通过给出两个结点的编号，表示这两个结点之间存在一条边。其中顶点从 1 到 N 编号。接下来一行给出一个正整数 K，表示查询的数量。然后是 K 行查询，每行以$n\ V_1\ V_2\cdots V_n$的格式给出一个顶点集合。

针对每个查询，如果是 Maximal Clique，输出Yes；如果不是 Clique，输出Not a Clique；否则输出Not Maximal。

数据规模

$$N\le 200$$

算法设计

针对给定的顶点集合，先用两重循环暴力枚举任意两个结点，判断这两个结点之间是否有边，如果没有边，显然该顶点集合一定不是 Clique，输出Not a Clique即可。如果是 Clique，遍历所有的顶点编号，判断该顶点能够到达顶点集合中的所有顶点，如果能，显然该顶点集合还可以加入顶点形成 Clique，所以该顶点集合不是 Maximal Clique，输出Not Maximal即可。否则的话，输出Yes。

C++代码

#include <bits/stdc++.h>
using namespace std;
using gg = long long;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    gg ni, mi, ki;
    cin >> ni >> mi;
    vector<unordered_set<gg>> graph(ni + 1);
    while (mi--) {
        gg ai, bi;
        cin >> ai >> bi;
        graph[ai].insert(bi);
        graph[bi].insert(ai);
    }
    cin >> mi;
    while (mi--) {
        cin >> ki;
        vector<gg> v(ki);
        for (gg& i : v) {
            cin >> i;
        }
        for (gg i = 0; i < v.size(); ++i) {  //判断每两个顶点之间是否有边
            for (gg j = i + 1; j < v.size(); ++j) {
                if (not graph[v[i]].count(v[j])) {
                    cout << "Not a Clique\n";
                    goto loop;
                }
            }
        }
        //判断是否有另一个顶点能够到达给定顶点集合中的所有顶点
        for (gg i = 1; i <= ni; ++i) {
            if (all_of(v.begin(), v.end(),
                       [&graph, &i](int a) { return graph[i].count(a); })) {
                cout << "Not Maximal\n";
                goto loop;
            }
        }
        cout << "Yes\n";
    loop:;
    }
    return 0;
}