题目粗心:
给定一个无向图G,顶点编号为1到Nv,Ne条边,判断给出的一组顶点汇合是否形成该图的一个极大齐全子图,如果是输入Yes,否则判断是否是一个齐全子图,如果是输入Not Maximal,否则输入Not a Clique。
算法思路:
首先得判断输出的汇合是否是以后图G的一个齐全子图,这里采纳isClique函数来实现,如果是就再判断是否是一个极大齐全子图,这里采纳isMaximal来实现,最初就依据判断的后果进行相应的输入就好。
isClique函数:
间接遍历输出汇合的不同顶点之间是否存在不邻接的点,如果是就返回false,否则返回true。
bool G[201][201];// 邻接矩阵,判断2点是否邻接 bool isClique(const vector<int> &a){ for(int i:a){ for(int j:a){ if(i!=j&&!G[i][j]){ // 存在不邻接的结点 return false; } } } return true;}
isMaximal函数:
咱们应用exist标记所有输出的结点,而后遍历所有的顶点,只有没有呈现在输出汇合中并且与汇合所有顶点都邻接,阐明不是极大齐全子图,返回false,否则返回true。
bool G[201][201];// 邻接矩阵,判断2点是否邻接 bool exist[201];// 标记每一个在subset中的结点编号 bool isMaximal(const vector<int> &a,int N){ for(int i=1;i<=N;++i){ if(exist[i]) continue; bool isAllAdjcent = true; for(int j:a){ // 得判断i和所有的点是否邻接 if(!G[i][j]){ isAllAdjcent = false; break; } } if(isAllAdjcent){ // 能够扩大一个邻接点 return false; } } return true;}
提交后果:
AC代码:
#include<cstdio>#include<vector>#include<cstring>using namespace std;bool G[201][201];// 邻接矩阵,判断2点是否邻接 bool exist[201];// 标记每一个在subset中的结点编号 bool isClique(const vector<int> &a){ for(int i:a){ for(int j:a){ if(i!=j&&!G[i][j]){ // 存在不邻接的结点 return false; } } } return true;}bool isMaximal(const vector<int> &a,int N){ for(int i=1;i<=N;++i){ if(exist[i]) continue; bool isAllAdjcent = true; for(int j:a){ // 得判断i和所有的点是否邻接 if(!G[i][j]){ isAllAdjcent = false; break; } } if(isAllAdjcent){ // 能够扩大一个邻接点 return false; } } return true;}int main(){ int Nv,Ne; scanf("%d %d",&Nv,&Ne); int a,b; for(int i=0;i<Ne;++i){ scanf("%d %d",&a,&b); G[a][b] = G[b][a] = true; } int M,N; scanf("%d",&M); for(int i=0;i<M;++i){ vector<int> subset; memset(exist,0,sizeof(exist)); scanf("%d",&N); for(int j=0;j<N;++j){ scanf("%d",&a); exist[a] = true; subset.push_back(a); } if(!isClique(subset)){ printf("Not a Clique\n"); }else if(!isMaximal(subset,Nv)) { printf("Not Maximal\n"); }else { printf("Yes\n"); } } return 0;}