yodgor mirzajonov_jacqueline novogratz

大家好，又见面了，我是你们的朋友全栈君。

1142. Maximal Clique (25)

• 题目： A clique is a subset of vertices of an undirected graph such that every two distinct vertices in the clique are adjacent. A maximal clique is a clique that cannot be extended by including one more adjacent vertex. (Quoted from https://en.wikipedia.org/wiki/Clique_(graph_theory)) Now it is your job to judge if a given subset of vertices can form a maximal clique. Input Specification: Each input file contains one test case. For each case, the first line gives two positive integers Nv (<= 200), the number of vertices in the graph, and Ne, the number of undirected edges. Then Ne lines follow, each gives a pair of vertices of an edge. The vertices are numbered from 1 to Nv. After the graph, there is another positive integer M (<= 100). Then M lines of query follow, each first gives a positive number K (<= Nv), then followed by a sequence of K distinct vertices. All the numbers in a line are separated by a space. Output Specification: For each of the M queries, print in a line “Yes” if the given subset of vertices can form a maximal clique; or if it is a clique but not a maximal clique, print “Not Maximal”; or if it is not a clique at all, print “Not a Clique”. Sample Input: 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 Sample Output: Yes Yes Yes Yes Not Maximal Not a Clique
• 分析： 该题是个公式题，完全图边和点有关系 a*(a-1)==e*2,不要使用a(a-1)/2,因为int因为精度损失，计算错误。 1,所以该题记录了边 2,最后一个测试点超时，cout引起，修改后通过千万别用cout/cin,数据量小的程序超时一半是这个造成
• code:

#include<iostream>
using namespace std;
int Nv,Ne;
#include<vector>
vector<int>edge;
#include<map>
#include<algorithm>
map<int,int>in;
int g[210];
bool isClique(int *a,int c)
{
int count=0;
int tmp=0;
for(int i=0;i<c;i++)
{
for(int j=i+1;j<c;j++)
{
int ta=a[i];
int tb=a[j];
if(ta==tb)continue;
else if(ta<tb)tmp=ta*1000+tb;
else tmp=tb*1000+ta;
if(in.find(tmp)!=in.end())count++;
//cout<<in.size()<<endl;
}
}
if(c*(c-1)==2*count)return true;
else return false;
}
bool isMax(int*a,int c)
{
int flag[210];
for(int i=0;i<c;i++)flag[a[i]]=1;
for(int i=1;i<=Nv;i++)
{
if(flag[i]==1)continue;
a[c]=i;
if(isClique(a,c+1)==true)return false;
}
return true;
}
int main()
{
freopen("in.txt","r",stdin);
// cin>>Nv>>Ne;
scanf("%d%d",&Nv,&Ne);
int a,b;
int tmp;
for(int i=0;i<Ne;i++)
{
//cin>>a>>b;
scanf("%d%d",&a,&b);
g[a]=g[b]=1;
if(a<b)tmp=a*1000+b;
else tmp=b*1000+a;
in[tmp]=1;
}
int M,c;
cin>>M;
int q[210];
for(int i=0;i<M;i++)
{
//cin>>c;
scanf("%d",&c);
for(int j=0;j<c;j++)
{
cin>>tmp;
q[j]=tmp;
}
if(isClique(q,c)==true)
{
if(isMax(q,c)==true)
//cout<<"Yes"<<endl;
printf("Yes\n");
else 
//cout<<"Not Maximal"<<endl;
printf("Not Maximal\n"); 
}   
else 
//cout<<"Not a Clique"<<endl;
printf("Not a Clique\n");
}
return 0;
}

版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。

发布者：全栈程序员栈长，转载请注明出处：https://javaforall.cn/188093.html原文链接：https://javaforall.cn