题目粗心:

给定一个无向图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;}