AcWing 1635. 最大团
原题链接
简单
作者:
RainSure
,
2022-03-01 09:04:50
,
所有人可见
,
阅读 164
判断最大团 要求团内任意两点都有直接的边相连
#include<iostream>
#include<cstring>
using namespace std;
const int maxn = 210;
bool st[maxn];
int g[maxn][maxn];
int nodes[maxn];
int n, m;
bool check_tuan(int cnt)
{
for(int i = 0; i < cnt; i ++){
for(int j = i + 1; j < cnt; j ++){
if(!g[nodes[i]][nodes[j]]) return false;
}
}
return true;
}
bool check_max(int cnt)
{
memset(st, 0, sizeof st);
for(int i = 0; i < cnt; i ++){
st[nodes[i]] = true;
}
for(int i = 1; i <= n; i ++){
if(!st[i]){
bool flag = true;
for(int j = 0; j < cnt; j ++){
if(!g[i][nodes[j]]){
flag = false;
break;
}
}
if(flag) return false;
}
}
return true;
}
int main()
{
cin >> n >> m;
while(m --)
{
int a, b; cin >> a >> b;
g[a][b] = g[b][a] = 1;
}
cin >> m;
while(m --)
{
int cnt; cin >> cnt;
for(int i = 0; i < cnt; i ++) cin >> nodes[i];
if(check_tuan(cnt)){
if(check_max(cnt)) cout << "Yes" << endl;
else cout << "Not Maximal" << endl;
}else cout << "Not a Clique" << endl;
}
return 0;
}