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)


相关推荐

  • redis一级缓存和二级缓存_面试官让面试者先回去

    redis一级缓存和二级缓存_面试官让面试者先回去说起mybatis,大家可能都知道它是一个优秀的久层框架,它支持定制化SQL、存储过程以及高级映射。面试中都会问起mybatis一级缓存和二级缓存,它体现出你对mybatis这个开发中的理解,如果照着答案背的话只能拿到一个及格分,所以今天咱们就好好聊聊mybatis。另外本人整理了20年面试题大全,包含spring、并发、数据库、Redis、分布式、dubbo、JVM、微服务等方面总结,下图是部分截图,需要的话点这里点这里,暗号CSDN。1.首先,什么是Mybatis?MyBatis是一.

  • execute executeupdate_executeupdate不执行

    execute executeupdate_executeupdate不执行增、删、改用executeUpdate()返回值为int型,表示被影响的行数例子查用executeQuery()返回的是一个集合.next()表示指针先下一行,还有first()指向第一行、last()指向最后一行、如果有数据就返回true…

  • 自动编码器—Autoencoder[通俗易懂]

    自动编码器—Autoencoder[通俗易懂]自动编码器DeepLearning最简单的一种方法是利用人工神经网络的特点,人工神经网络(ANN)本身就是具有层次结构的系统,如果给定一个神经网络,我们假设其输出与输入是相同的,然后训练调整其参数,得到每一层中的权重。自然地,我们就得到了输入I的几种不同表示(每一层代表一种表示),这些表示就是特征。自动编码器就是一种尽可能复现输入信号的神经网络。为了实现这种复现,自动编码器就

  • C语言实现五子棋小游戏

    C语言实现五子棋小游戏三子棋,五子棋,无论多少子棋,其原理都是一样的。下面我用五子棋为例讲解用C语言多文件编程实现五子棋。设计电脑和玩家两个作为下棋的两方,用键盘输入作为玩家的游戏操作。1.效果图:程序总的构架:我们只要输入坐标就可以和电脑对弈了。电脑的棋子用‘0’表示,玩家的棋子用‘x’表示。2.打印菜单可以根据自己的爱好设计各种风格的…

  • 用Attributes.Add添加事件

    用Attributes.Add添加事件1、(textbox2.Visible=true)JS的寫法:    textbox2.Attributes.Add(“onfocus”,”document.getElementById(‘textbox2’).style.display=”);2、(textbox2.Visible=false)JS的寫法:    textbox2.Attributes.Add(“onfocus”,”document.getElementById(‘textbox2’).style.display=’no

  • Windows服务器如何修改SQL server内存大小等设置

    Windows服务器如何修改SQL server内存大小等设置

发表回复

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

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