Self-Assembly(UVA 1572)-程序员宅基地

技术标签: 算法  深度优先  图论  

网址如下:

Self-Assembly - UVA 1572 - Virtual Judge (vjudge.net)

(第三方网站)

垃圾校园网,交个代码花了一堆时间

一道求存在有向循环图的题,刚开始关系理解错了,搞得写了很久

就是把字母作为节点,长方形作为边,构建有向图

然后拓扑排序,存在有向环则输出

代码如下:

#include<cstdio>
#include<cstring>
bool scanf_input(void);
void initialize(void);
bool dfs(int u);
bool toposort(void);
bool G[53][53], is_exist[53];
int c[53], n;

int main(void)
{
    initialize();
    while(scanf_input()){
        if(toposort()) printf("bounded\n");
        else printf("unbounded\n");
        initialize();
    }

    return 0;
}
bool scanf_input(void)
{
    if(scanf("%d", &n) != 1) return false; getchar();
    for(int i = 0; i < n; i++){
        int id1[4], id2[4];
        for(int j = 0; j < 4; j++){
            char c1 = getchar(), c2 = getchar();
            if(c1 == '0') id1[j] = id2[j] = 0;
            else{
                id1[j] = id2[j] = c1 - 'A' + 1;
                if(c2 == '+') id2[j] += 26;
                else id1[j] += 26;
                is_exist[id1[j]] = true;
            }
        }
        for(int u = 0; u < 3; u++)
            for(int v = u + 1; v < 4; v++)
                G[id1[u]][id2[v]] = G[id1[v]][id2[u]] = true;
        getchar();
    }
    return true;
}
void initialize(void)
{
    memset(G, 0, sizeof(G)); memset(is_exist, 0, sizeof(is_exist));
}
bool dfs(int u)
{
    c[u] = -1;
    for(int v = 1; v <= 52; v++){
        if(is_exist[v] && G[u][v]){
            if(c[v] == -1) return false;
            else if(!c[v] && !dfs(v)) return false;
        }
    }
    c[u] = 1;
    return true;
}
bool toposort(void)
{
    memset(c, 0, sizeof(c));
    for(int u = 1; u <= 52; u++)
        if(is_exist[u] && !c[u]) if(!dfs(u)) return false;
    return true;
}

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/Fool256353/article/details/136996838

智能推荐

2.4G SOC收发芯片XL2412P,适用于无线键鼠,遥控器等多种场景-程序员宅基地

文章浏览阅读203次,点赞3次,收藏2次。XL2412P芯片是-款高性能低功耗的SOC集成无线收发芯片,集成MO核MCU,工作在2.400~2.483GHz世界通用ISM频段。该芯片集成了射频接收器、射频发射器、频率综合器、GFSK 调制器、GFSK解调器等功能模块,并且支持一对多线网和带ACK的通信模式。容易过FCC等认证。嵌入了24Kbytes flash和3Kbytes SRAM存储器,最高工作频率24MHz。芯片集成多路12C、USART等通讯外设, 1路12bit ADC, 2个16bit定时器,以及2路比较器。电视和机顶盒遥控器;

树莓派4 将sd卡镜像拷贝到usb ssd后无法启动ubuntu_树莓派ubuntu的sd卡复制到另一张sd卡上-程序员宅基地

文章浏览阅读245次。主要问题在于kernel启动文件没有解压,和启动文件设置问题。解决办法参考https://jamesachambers.com/raspberry-pi-4-ubuntu-20-04-usb-mass-storage-boot-guide。_树莓派ubuntu的sd卡复制到另一张sd卡上

[nginx] “nginx日志自动拆分“踩坑记_nginx testing existence failed-程序员宅基地

文章浏览阅读519次,点赞12次,收藏7次。existence failed (2: No such file or directory) while logging request_nginx testing existence failed

ValueError: Could not import faiss python package. Please install it with pip install faiss解决方案_importerror: could not import faiss python package-程序员宅基地

文章浏览阅读7.6w次,点赞11次,收藏11次。本文主要介绍了ValueError: Could not import faiss python package. Please install it with pip install faiss解决方案,希望能对学习faiss的同学们有所帮助。文章目录1. 问题描述2. 解决方案_importerror: could not import faiss python package. please install it with `

ElasticSearch监控工具 - cerebro_cerebro对es发起查询-程序员宅基地

文章浏览阅读1.4k次。之前一直用的head查看索引,还有kibana,最近发现一个比较牛逼的监控工具——cerebro,传说中的高富帅,一起来体验下:安装也很简单,网上一大把。首秀极具神秘高雅感觉,让人瞬间有了反应。连接客户端地址后进行以下界面:太清楚了,节点数,分片数,副本,节点cpu使用,磁盘使用,数据量等等信息一目了然,真的是相见恨晚呀以上就是它的风采。上面的配置..._cerebro对es发起查询

(免费领源码)java#springboot#mysql医疗产品销售系统01474-计算机毕业设计项目选题推荐-程序员宅基地

文章浏览阅读24次。本文以选择Eclipse开发工具的java开发语言中springboot+mysql数据库来存储数据,以B/S为运行模式,开发了一个医疗产品销售系统,划分为了管理员、普通用户两种角色,实现了对医疗产品信息的查询、分类管理、产品管理、产品入库、产品出库等功能模块。经过了多次的测试和结果评估,该医疗产品销售系统已经能够满足医疗产品销售系统的实际应用的需要并可以成功上线运行使用了。

随便推点

生鲜电商市场消费者调查方案_某电商网站准备进入生鲜电商领域,希望了解该市场的市场发展趋势请撰写采集方-程序员宅基地

文章浏览阅读226次。通过本次调查,民安智库(北京第三方农贸市场环境测评)将全面了解某省生鲜电商消费者的基本情况、购买习惯和消费偏好,为生鲜电商平台提供有针对性的改进建议,助力企业提升竞争力,把握市场发展机遇。3. 探讨该省生鲜电商消费者对现有生鲜电商平台的满意度和改进意见,通过收集和分析消费者的反馈,我们可以了解到他们对于生鲜电商平台的满意程度以及对于平台改进的建;1. 了解该省生鲜电商消费者的基本信息,如年龄、性别、职业、收入等,帮助客户更好地理解消费者的购买能力和消费习惯;4. 预测该省生鲜电商市场的发展趋势和潜在商机。_某电商网站准备进入生鲜电商领域,希望了解该市场的市场发展趋势请撰写采集方

LibreOffice 源码编译_libreoffice编译-程序员宅基地

文章浏览阅读5k次。环境部署 LibreOffice(简称"LO")的编译是在Windows系统下模拟unix环境的cygwin中进行,所以同时也需要载很多该环境下的各种包。起初在部署环境时,不清楚编译时具体需要用到哪些包,就只安装cygwin时默认的一些,然后就开始配置编译选项,之后根据编译过程中的提示缺少哪些包,一步一步去手动下载。后来,看到LO的社区网站上(https://wiki.documentf_libreoffice编译

防XSS攻击之特殊字符转换为html实体_xss攻击特殊字符-程序员宅基地

文章浏览阅读2.7k次。什么是XSS攻击,比如,比如,我们把网站发布在网上,有一些恶意的用户在提交数据的时候会在表单输入js,css.a标签之类的这些html语言,然后这些数据被保存到数据库,那么我们要调用这些数据的时候,这些数据被原封不动的被呈现在网页上,这些数据是可以被html所识别的,届时我的的页面就会变得乱七八糟的。怎么解决呢,我们只要在这些数据没有插入数据库前调用php内置函数将这些特殊的字符转换为html..._xss攻击特殊字符

对称矩阵的压缩存储_对称矩阵需要的存储空间为-程序员宅基地

文章浏览阅读1.3k次。对于对称矩阵,可以为每一对对称元分配一个存储空间,可以将n^2个元压缩存储在n(n+1)/2个元的空间中_对称矩阵需要的存储空间为

Leo赠书活动-16期 名校毕业生教材-程序员宅基地

文章浏览阅读2.1k次,点赞67次,收藏48次。以上便是本文的全部内容,本人才疏学浅,文章有什么错误的地方,欢迎大佬们批评指正!我是Leo,一个在互联网行业的小白,立志成为更好的自己。如果你想了解更多关于Leo,可以关注公众号-程序员Leo,后面文章会首先同步至公众号。

IntelliJ IDEA 2022.2 (Ultimate Edition) plugin插件开发_cannot resolve the latest gradle intellij plugin v-程序员宅基地

文章浏览阅读2.2k次。不用添加plugin configution 配置,直接点击gradle run plugin脚本即可。这里默认创建的iml文件module type有问题,需要修改为PLUGIN_MODULE。升级org.jetbrains.intellij 版本到最新1.9.0版本,避免采坑。可能因为github请求超时导致如下报错,忽略即可。替换为aliyun镜像加快构建速度。_cannot resolve the latest gradle intellij plugin version

推荐文章

热门文章

相关标签