题意
给出一个无向图，给出m组顶点集，判断。
思路
cnt[id]非常关键，否则后面遍历cnt对该组进行判定的时候，cnt可能会不包含in_vertices中的某些key，而算法正确的前提是cnt要包含in_vertices中所有的key。
#include "bits/stdc++.h"
using namespace std;
const int N = 210;
vector<int> links[N];
int main(){
// freopen("input.txt","r",stdin);int nv, ne; scanf("%d%d",&nv,&ne);for (int i = 0; i < ne; ++i) {int a,b; scanf("%d%d",&a,&b);links[a].push_back(b); links[b].push_back(a);}int m; scanf("%d",&m);for (int i = 0; i < m; ++i) {int k; scanf("%d",&k);map<int,int> cnt, in_vertices;for (int j = 0; j < k; ++j) {int id; scanf("%d",&id); in_vertices[id] = 1,cnt[id];for(int t:links[id]) cnt[t] ++;}bool not_clique = false, not_maximal = false;for(auto &entry:cnt){if (in_vertices.count(entry.first) && entry.second != k-1) {not_clique = true;break;}else if (!in_vertices.count(entry.first) && entry.second == k){not_maximal = true;}}if (not_clique) printf("Not a Clique\n");else if (not_maximal) printf("Not Maximal\n");else printf("Yes\n");}
}
Sample Input:
8 10
5 6
7 8
6 4
3 6
4 5
2 3
8 2
2 7
5 3
3 4
6
4 5 4 3 6
3 2 8 7
2 2 3
1 1
3 4 3 6
3 3 2 1
Sample Output:
Yes
Yes
Yes
Yes
Not Maximal
Not a Clique