poj 1094 Sorting It All Out (拓扑排序)

poj 1094 Sorting It All Out (拓扑排序)

大家好,又见面了,我是全栈君,今天给大家准备了Idea注册码。

链接:poj 1094

题意:给定一系列关系(仅仅存在大写字母),推断是否存在矛盾,

或无法确定关系。或能够确定唯一的关系

分析:利用拓扑排序。可是须要边输入关系边排序

矛盾:推断是否存在环

确定关系:能找出唯一的拓扑排序

不能确定关系:不存在环,且全部关系处理后,关系仍无法确定

注:假设出现矛盾,则无需推断接下来的关系了

#include<stdio.h>
#include<string.h>
int n,m,vis[30],rd[30],flag[30],map[30][30],cnt;
char t[30];
int tpsort()
{
    int i,j,k,num,mark=1;
    cnt=0;
    memset(vis,0,sizeof(vis)); //标记是否訪问
    for(i=0;i<n;i++)
        if(flag[i]){
            num=0;
            for(j=0;j<n;j++)    //计算入度为0的个数
                if(flag[j]&&!rd[j]&&!vis[j])
                    num++;     
            if(num==0)  //若不存在入度为0结点,则存在环
                return 0;
            if(num>1)   //若入度为0的结点大于1。说明无法确立唯一的拓扑关系
                mark=0;
            for(j=0;j<n;j++){
                if(flag[j]&&!rd[j]&&!vis[j]){
                    t[cnt++]=j+'A';
                    vis[j]=1;
                    break;
                }
            }
            for(k=0;k<n;k++)
                if(map[j][k])
                    rd[k]--;
        }
    if(!mark)
        cnt=0;
    return 1;
}
int main()
{
    int i,j,mark,pos,r[30];
    char s[5];
    while(scanf("%d%d",&n,&m)!=EOF){
        if(m==0&&n==0)
            break;
        mark=1;
        memset(map,0,sizeof(map));
        memset(flag,0,sizeof(flag)); //标记该元素是否存在
        memset(r,0,sizeof(r));
        for(i=1;i<=m;i++){
            scanf("%s",s);
            if(mark==1){
                flag[s[0]-'A']=flag[s[2]-'A']=1;
                if(s[1]=='>'){
                    map[s[2]-'A'][s[0]-'A']=1;  //记录边的关系
                    r[s[0]-'A']++;              //记录入度
                }
                else{
                    map[s[0]-'A'][s[2]-'A']=1;
                    r[s[2]-'A']++;
                }
                for(j=0;j<n;j++)
                    rd[j]=r[j];   //辅助空间。防止过程中拓扑排序将入度改变了
                mark=tpsort(); 
                if(!mark)   
                    pos=i;
                if(mark&&cnt==n){  //当没有出现环且关系都确定
                    mark=2;
                    pos=i;
                    t[cnt]=0;  //字符数组最后附空字符
                }
            }
        }
        if(mark==0)
            printf("Inconsistency found after %d relations.\n",pos);
        else if(mark==1)
            printf("Sorted sequence cannot be determined.\n");
        else if(mark==2)
            printf("Sorted sequence determined after %d relations: %s.\n",pos,t);
    }
    return 0;
}

版权声明:本文博主原创文章。博客,未经同意不得转载。

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

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/116980.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • java找不着符号_找不到符号:Java

    java找不着符号_找不到符号:Java如果这是一个怪异的问题,我感到很抱歉,但是我刚刚开始OOP,并遇到了一个我应该制作的简单菜单驱动数学程序。我清除了编译器给我的所有错误,但是现在它给了我大约14个新错误,其中大多数被描述为“找不到符号”。这是我的代码:importjava.util.Scanner;publicclassMathMenu{//MENUMETHODprivatestaticvoidmenu(String…

  • 如何划分音节并区分重读和非重读单词_重读音节符号怎么标

    如何划分音节并区分重读和非重读单词_重读音节符号怎么标这里涉及到了英语里的双音节和多音节的知识一、双音节单词的音节划分方法可归纳为“两分手.一归前或一归后”.1.“两分手”是指:当两个元音之间有两个辅音字母时,将两个辅音字母划分在前后两个音节里.具体

  • Mysql 多表连接查询

    Mysql 多表连接查询本文部分内容转载至:Mysql多表查询详解,同时感谢原作者的整理与创作;

  • Minicom使用介绍

    Minicom使用介绍minicom是一个串口通信工具,就像Windows下的超级终端。可用来与串口设备通信,如调试交换机和Modem等。一、Minicoms使用1.安装minicom打开终端sudoapt-getinstallminicom即可完成安装。2.minicom配置参数命令运行sudominicom-s进入了minicom的配置界面:使用上下键选择Serialports…

  • 喊山第二部_喊山主演

    喊山第二部_喊山主演原题链接喊山,是人双手围在嘴边成喇叭状,对着远方高山发出“喂—喂喂—喂喂喂……”的呼唤。呼唤声通过空气的传递,回荡于深谷之间,传送到人们耳中,发出约定俗成的“讯号”,达到声讯传递交流的目的。原来它是彝族先民用来求援呼救的“讯号”,慢慢地人们在生活实践中发现了它的实用价值,便把它作为一种交流工具世代传袭使用。(图文摘自:http://news.xrxxw.com/newsshow-8018.html)一个山头呼喊的声音可以被临近的山头同时听到。题目假设每个山头最多有两个能听到它的临近山头。给定任意一个发

  • GridLayout用法「建议收藏」

    GridLayout用法「建议收藏」概述  在Android中,使用的最多的布局是LinearLayout了,它可以让布局界面中的子控件以常见的方式比如水平或者垂直方向对齐。在使用LinearLayout时,开发者应该会记得,会经常遇到复杂的布局结构,所以会时常使用各种LinearLayout进行嵌套,而且应该注意嵌套层次不要过多。  有很多不错的文章(比如有:AndroidLayoutTricks#1,Flattening

发表回复

您的电子邮箱地址不会被公开。

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