首先判断是否是团:在一个无向图中,如果一个顶点子集满足子集内的任意两个不同顶点之间都是相连的,那么这个顶点子集就被称为一个团。
即若对于所有i,j满足(j < i,0 < i < k),g[ver[i]][ver[j]]
都成立,则这个顶点子集就被称为一个团,则只要有一个组合(i,j),g[ver[i]][ver[j]]
不成立,则这个顶点子集就不是一个团
判断是否是最大团:如果一个团不能通过加入某个新的顶点来扩展成一个更大的团,那么该团就被称为最大团。即如果一个团能通过加入某个新的顶点来扩展成一个更大的团,那么该团就不是最大团。
首先先枚举加入的新顶点,然后枚举顶点子集ver[]中的点,判断一下条件:
即(g[1][ver[0]] && g[1][ver[1]] && g[1][ver[2]] && ... g[1][ver[k - 1]]) || (g[2][ver[0]] && g[2][ver[1]] && ... g[2][ver[k - 1]]) || ... || (g[n][ver[0]] && g[n][ver[1]] && ... g[n][ver[k - 1]])
成立,则该团就不是最大团,即以||
分隔的只要有一个条件成立,则该团就不是最大团
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 210;
bool g[N][N];// 领接矩阵
bool st[N];// 某个顶点是否在顶点集当中
int ver[N];// 存储顶点集
int n,m;
int k;
bool check_clique(){// 判断是否是团
for(int i = 0;i < k;i ++){
for(int j = 0;j < i;j ++){
if(!g[ver[i]][ver[j]]){
return false;
}
}
}
return true;
}
bool check_max_clique(){// 判断是否是最大团
for(int i = 1;i <= n;i ++){// 枚举加入的新顶点
if(st[i]) continue;
bool flag = true;
for(int j = 0;j < k;j ++){// 枚举顶点子集ver[]中的点
if(!g[i][ver[j]]) {
flag = false;
break;
}
}
if(flag){
return false;
}
}
return true;
}
int main()
{
cin >> n >> m;
for(int i = 0;i < m;i ++){
int x,y;
cin >> x >> y;
g[x][y] = g[y][x] = true;
}
int q;
cin >> q;
while(q --){
memset(st, 0, sizeof(st));
cin >> k;
for(int i = 0;i < k;i ++){
int x;
cin >> x;
ver[i] = x;
st[x] = true;
}
if(check_clique()){
if(check_max_clique()){
printf("Yes\n");
}
else{
printf("Not Maximal\n");
}
}
else{
printf("Not a Clique\n");
}
}
return 0;
}