这道题耗了我两个多小时,真的太菜了!
这道题写错的几个地方:
1.判断相等,我写成了赋值符号。
2.忽略了编号是从1开始的。
#include<cstdio>
#include<vector>
#include<algorithm>
#include<cstring>
#include<iostream>
using namespace std;
const int maxn=205;
const int INF = 0x3f3f3f3f;
int edge[maxn][maxn];
int n,m;
bool clique(vector<int> v){
for(int i=0;i<v.size();i++){
for(int j=i+1;j<v.size();j++){
if(edge[v[i]][v[j]]==INF) return false;
}
}
return true;
}
bool maxclique(vector<int> v,int hash[]){
bool notmaximal;
for(int i=1;i<=n;i++){
if(hash[i] == 1) continue; //从其他点里取
notmaximal = false;
for(int j=0;j<v.size();j++){
if(edge[i][v[j]] == INF) notmaximal=true;
}
if(notmaximal==false) return notmaximal; //这里可以再添加一个点进团,所以直接返回不是最大团
}
return notmaximal;
}
int main(){
cin>>n>>m;
int u,v;
fill(edge[0],edge[0]+maxn*maxn,INF);
for(int i=0;i<m;i++){
cin>>u>>v;
edge[u][v]=1;
edge[v][u]=1;
}
int t,k;
cin>>t;
vector<int> cur;
int hash[220];
for(int i=0;i<t;i++){
cin>>k;
cur.clear();
memset(hash,0,sizeof(hash));
for(int j=0;j<k;j++){
cin>>u;
cur.push_back(u);
hash[u]=1;
}
//先判定是否是clique
if(clique(cur)){
if(maxclique(cur,hash)) printf("Yes\n");
else printf("Not Maximal\n");
}
else printf("Not a Clique\n");
}
return 0;
}