题目描述

最大团判断  统计是否连接 通过邻接矩阵储存

算法1

C++ 代码

#include<iostream>
#include<cstring>
using namespace std;
const int N=210;
int g[N][N];
int n,m;
int cnt[N],clique[N];

void query(int p){
    memset(cnt,0,sizeof(cnt));

    for(int i=0;i<p;i++){
        for(int j=i+1;j<p;j++){
            if(!g[clique[i]][clique[j]]){
                cout<<"Not a Clique"<<endl;
                return ;
            }
        }
    }

    //判是否是最大团
    //及判断是否有其他节点与给定所有节点都有边
    for(int i=0;i<p;i++){
        for(int j=1;j<=n;j++){
            if(g[clique[i]][j]){
                cnt[j]++;
            }
        }
    }

    for(int i=0;i<p;i++){
        cnt[clique[i]]=0;  //保证新加入的点不是原来团中的点
    }

    bool flag=true;
    for(int j=1;j<=n;j++){
        if(cnt[j]==p){
            flag=false;
            break;
        }
    }
    if(flag){
        cout<<"Yes"<<endl;
    }else{
        cout<<"Not Maximal"<<endl;
    }
}

int main(){
    cin>>n>>m;

    for(int i=0;i<m;i++){
        int a,b;
        cin>>a>>b;
        g[a][b]=g[b][a]=1;
    }

    int k;
    cin>>k;
    for(int i=0;i<k;i++){
        memset(clique,0,sizeof(clique));
        int p;
        cin>>p;
        for(int j=0;j<p;j++){
            cin>>clique[j];
        }

        query(p);

    }

    return 0;
}