PAT甲级1142.

目录

A1142

题目

样例

输入:

8 10
5 6
7 8
6 4
3 6
4 5
2 3
8 2
2 7
5 3
3 4
6
4 5 4 3 6
3 2 8 7
2 2 3
1 1
3 4 3 6
3 3 2 1

输出:

Yes
Yes
Yes
Yes
Not Maximal
Not a Clique

思路和坑点

　　思路:
　　首先明确概念：clique指的是图的某一个顶点的子集中，任意两个顶点之间都相互邻接。maximal clique指的是clique的最大集合，不能再找到一个顶点加入maximal clique以满足clique的要求。
　　由此，可以得到思路，默认是clique，当发现有不邻接的定点对儿时，则不是一个clique，然后再判断是不是maxiaml，判断是否存在一个不在集合中的点，满足和当前集合中所有顶点都邻接，如果能找到则不是maximal。

AC代码

#include<bits/stdc++.h>
using namespace std; 
#define MAXN 205 
int G[MAXN][MAXN]={0};
int n,m;
void Judge();
int main(){    
#ifdef ONLINE_JUDGE    
#else    
    freopen("1.txt", "r", stdin);    
#endif    
    int a,b,k;
    scanf("%d%d",&n,&m);
    for(int i=0;i<m;i++){
        scanf("%d%d",&a,&b);
        G[a][b]=G[b][a]=1;
    }
    scanf("%d",&k);
    for(int i=0;i<k;i++)
        Judge();
    return 0;    
}
void Judge()
{
    int flag=0;                     //0表示yes，1表示not max，2表示not clique 
    vector<bool> vis(n);
    fill(vis.begin(),vis.end(),false);//所有的顶点的访问标记
    int num;
    scanf("%d",&num);
    vector<int> vn(num);            //读入一组结点
    for(int i=0;i<num;i++){
        scanf("%d",&vn[i]);
        vis[vn[i]]=true;
    }
    for(int i=0;i<num;i++){        //如果出现两个顶点之间不连通便是2 
        for(int j=i+1;j<num;j++){
            if(G[vn[i]][vn[j]]==0){
                flag=2;
                break;
            }    
        }
        if(flag==2) break; 
    }
    if(flag==0){                    //如果不是2，则继续判别
        for(int i=1;i<=n;i++){
            int cnt=0;              //计数器
            if(vis[i]==false){      //检测不在当前集合中的的顶点
                for(int j=0;j<vn.size();j++)
                    if(G[i][vn[j]]==1) cnt++; //统计结点i和当前集合中的链接个数
                if(cnt==vn.size()){ //如果结点i能够和当前集合中所有结点想邻接，则说明当前集合可以扩充，不是max，标记为1
                    flag=1; break;
                }
            }
        }
    }
    switch(flag){                   //根据标记输出类型
        case 0:puts("Yes");break;
        case 1:puts("Not Maximal");break;
        case 2:puts("Not a Clique");break;
        default: break;
    }
}