yodgor mirzajonov_jacqueline novogratz

yodgor mirzajonov_jacqueline novogratz1142.MaximalClique(25)题目:Acliqueisasubsetofverticesofanundirectedgraphsuchthateverytwodistinctverticesinthecliqueareadjacent.Amaximalcliqueisacliquethatcannotbee…

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新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;
}
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请联系我们举报,一经查实,本站将立刻删除。

发布者:全栈程序员-站长,转载请注明出处:https://javaforall.net/188093.html原文链接:https://javaforall.net

(0)
全栈程序员-站长的头像全栈程序员-站长


相关推荐

  • 学生用vs哪个版本_vs2008激活成功教程版

    学生用vs哪个版本_vs2008激活成功教程版以下内容都是转来的,等有时间我会自己整合一下(来源)最近家里的机器重装系统,又得装吃饭的家伙——VS2005了。自从上半年MS出了VS2005的SP1之后,装了几次SP1都觉得挺噩梦的,太长时间了。所以这次参考了网上的一些内容,制作了VS2005的SP1集成版,Professional和TeamSuite各一份。主要还是5步吧,参考了网上的很多资料1把VS…

    2022年9月1日
    2
  • 什么是redis

    什么是redis

    2021年10月18日
    49
  • java session有效期设置方式「建议收藏」

    java session有效期设置方式「建议收藏」session默认有效期是30分钟,设置session的有效期有三种方法:1.在tomcat中的server.xml中定义:在tomcat中的conf/server.xml文件可以修改服务器上的所有程序的默认有效期,设置单位为毫秒,定义代码如下:<Contextpath=”/test”docBase=”/test”  defaultSessionTimeOut=”360…

    2022年7月12日
    14
  • redis 乐观锁_redis 乐观锁

    redis 乐观锁_redis 乐观锁文章目录GeospatialHyperloglogBitmapsRedis事务悲观锁和乐观锁JedisSpringboot继承RedisGeospatial存储地理位置的数据结构应用场景朋友的定位,附近的人,打车距离计算Geospatial底层使用的是Zset127.0.0.1:6379> geoadd city 116.23 40.22 beijing 添加一个数据127.0.0.1:6379> geoadd city 121.47 31.23 shanghai 118.77

    2022年8月9日
    3
  • 8个高质量图标的最佳搜索引擎

    8个高质量图标的最佳搜索引擎

    对于每个网站开发者来说,设计是很重要的一部分。图标是设计中一个环节。你可以找到许多集合图标的网站。但很难找到免费的高质量图标。这是我在此分享一些免费的高质量图标搜索引擎的原因。你要访问这些引擎以找到高质量图标。如果你知道更多的网站,也请与我们分享!
    IconFinder
    以简便并且有效的方式为网站设计者和开发人员提供高质量的图标。

    Iconlet
    是一个单纯的免费图标和图像的搜索引擎。

    IconScan

    2022年5月23日
    55
  • 2022新UI美观发卡网源码下载+功能强大且齐全

    2022新UI美观发卡网源码下载+功能强大且齐全正文:程序没有更多的介绍,总的来说就是2022最新版本的,美观功能齐全无BUG,上传程序后,运行目录public,伪静态thinkPHP,域名/install.php进行安装,就是这么简单哈,程序没有马赛克的演示图我就放压缩包了,大家自行去查看吧。程序:lanzou.com/ieWX005hj7dc图片:…

    2022年7月14日
    20

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

关注全栈程序员社区公众号