PAT 1142. 最大团
原题链接
简单
作者:
YAX_AC
,
2024-11-18 09:27:14
,
所有人可见
,
阅读 2
//clique小集团 subset子集 such that使得满足…的条件 distinct不同的 adjacent相邻
//sequence序列,顺序,次序,一系列,一连串 a pair of 一对,一双 a pair of vertices of an edg一对边的顶点
//A clique is a subset of vertices of an undirected graph
//such that every two distinct vertices in the clique are adjacent.
//团是无向图的顶点子集,使得团中的每两个不同顶点都是相邻的。
//A maximal clique is a clique that cannot be extended by including one more adjacent vertex.
//如果一个团不能通过加入某个新的顶点来扩展成一个更大的团,那么该团就被称为最大团。
//then followed by a sequence of K distinct vertices.
//然后是K个不同顶点的序列。
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 250;
int n,m,k;
int vers[N];
bool st[N];
int g[N][N];
bool check_clique(int cnt) //判断是不是团
{
for(int i= 0; i<cnt; i++)
for(int j = 0; j<i; j++)
if(!g[vers[i]][vers[j]])
return false;
return true;
}
//如果一个团不能通过加入某个新的顶点来扩展成一个更大的团,那么该团就被称为最大团
//确认不能加入新的点
bool check_max(int cnt) //判断是不是最大团
{
memset(st,0,sizeof st);
for(int i = 0; i<cnt; i++)
st[vers[i]] = true;//旧的点标记为1
for(int i = 1; i<=n; i++)
if(!st[i])//新的点
{
bool success = true;
for(int j = 0; j<cnt; j++)
if(!g[i][vers[j]])
{
success = false;
break;
}
if(success) 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>>k;
while(k--)
{
int cnt;
cin>>cnt;
for(int i = 0; i<cnt; i++) cin>>vers[i];
if(check_clique(cnt))
{
if(check_max(cnt)) puts("Yes");
else puts("Not Maximal");
}
else puts("Not a Clique");
}
return 0;
}