yodgor mirzajonov_jacqueline novogratz

大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE稳定放心使用

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;
}