Sorting It All Out

Sorting It All Out

Description

An ascending sorted sequence of distinct values is one in which some form of a less-than operator is used to order the elements from smallest to largest. For example, the sorted sequence A, B, C, D implies that A < B, B < C and C < D. in this problem, we will give you a set of relations of the form A < B and ask you to determine whether a sorted order has been specified or not.

Input

Input consists of multiple problem instances. Each instance starts with a line containing two positive integers n and m. the first value indicated the number of objects to sort, where 2 <= n <= 26. The objects to be sorted will be the first n characters of the uppercase alphabet. The second value m indicates the number of relations of the form A < B which will be given in this problem instance. Next will be m lines, each containing one such relation consisting of three characters: an uppercase letter, the character “<” and a second uppercase letter. No letter will be outside the range of

the first n letters of the alphabet. Values of n = m = 0 indicate end of input.

Output

For each problem instance, output consists of one line. This line should be one of the following three:

Sorted sequence determined after xxx relations: yyy…y. Sorted sequence cannot be determined. Inconsistency found after xxx relations.

where xxx is the number of relations processed at the time either a sorted sequence is determined or an inconsistency is found, whichever comes first, and yyy…y is the sorted, ascending sequence.

Sample Input

4 6
A<B
A<C
B<C
C<D
B<D
A<B
3 2
A<B
B<A
26 1
A<Z
0 0

Sample Output

Sorted sequence determined after 4 relations: ABCD.
Inconsistency found after 2 relations.
Sorted sequence cannot be determined.



 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<map>
 6 #include<set>
 7 #include<stack>
 8 #include<queue>
 9 #include<vector>
10 using namespace std;
11 const int ms=26;
12 int n,m;
13 bool appear[ms];
14 char output[ms+1];
15 int cnt[ms];
16 int tmp[ms];
17 vector<vector<char> > v;
18 int topo_sort(int s)
19 {
20     int i,j,k,flag=1;
21     int total=0,r=0;
22     for(i=0;i<n;i++)
23         tmp[i]=cnt[i];
24     while(s--)
25     {
26         total=0;
27         for(i=0;i<n;i++)
28             if(appear[i]&&tmp[i]==0)
29             {
30                 j=i;
31                 total++;
32             }
33         if(total>=1)
34         {
35             if(total>1)
36                 flag=0;
37             for(i=0;i<v[j].size();i++)
38                 tmp[v[j][i]]--;
39             tmp[j]=-1;
40             output[r++]=j+'A';
41             output[r]=0;
42         }
43         else
44             return -1;
45     }
46     if(flag)
47         return r;
48     return 0;
49 }
50 int main()
51 {
52     int i,j,k,judge,det;
53     char str[4];
54     while(scanf("%d%d",&n,&m)==2&&(n+m))
55     {
56         judge=0;
57         det=0;
58         int sum=0;
59         v.clear();v.resize(n);
60         memset(cnt,0,sizeof(cnt));
61         memset(appear,false,sizeof(appear));
62         for(i=1;i<=m;i++)
63         {
64             scanf("%s",str);
65             cnt[str[2]-'A']++;
66             v[str[0]-'A'].push_back(str[2]-'A');
67             if(!appear[str[0]-'A'])
68             {
69                 sum++;
70                 appear[str[0]-'A']=1;
71             }
72             if(!appear[str[2]-'A'])
73             {
74                 sum++;
75                 appear[str[2]-'A']=1;
76             }
77             if(judge==0)
78             {
79                 det=topo_sort(sum);
80                 if(det==-1)
81                 {
82                     judge=-1;k=i;
83                 }
84                 else if(det==n)
85                 {
86                     judge=1;
87                     k=i;
88                 }
89             }
90         }
91         if(judge==-1)
92             printf("Inconsistency found after %d relations.\n",k);
93         else if(judge==0)
94             printf("Sorted sequence cannot be determined.\n");
95         else
96             printf("Sorted sequence determined after %d relations: %s.\n",k,output);
97     }
98     return 0;
99 }

 

转载于:https://www.cnblogs.com/767355675hutaishi/p/4078447.html

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

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

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

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

(0)


相关推荐

  • 布隆过滤器原理及应用场景分析_布隆过滤器 数据更新怎么办

    布隆过滤器原理及应用场景分析_布隆过滤器 数据更新怎么办https://www.cnblogs.com/qdhxhz/p/11237246.html开发一个电商项目,因为数据量一直在增加(已达亿级),所以需要重构之前开发好的秒杀功能,为了更好的支持高并发,在验证用户是否重复购买的环节,就考虑用布隆过滤器。也顺便更加深入的去了解下布隆过滤器的原理,感觉还是蛮有意思的,这一连串的公式不静下心来思考,很容易被绕晕。一、概述1、什么是布隆过滤器本质上布隆过滤器是一种数据结构,比较巧妙的概率型数据结构,特点是高效地插入和查询。根据查询结果可以用来告

  • XSHELL安装指南

    XSHELL安装指南开发环境部署目的:利用ssh远程登陆服务器(在windows系统下远程连接linux)下载XSHELL7XSHELL7下载网址:https://www.netsarang.com/zh/xshell/点击“下载”点击“免费授权界面”以上是XSHELL7的下载过程然后找到右键“以管理员身份运行”一上来会出现这种错误,先点击“是(Y)”过程中一直点击“下一步”,以及“我同意”类似的,然后选择个安装路径就可以没啥特殊的。到最后一切顺利的话会显示下面这样的界面一般通向成功的道

    2022年10月31日
  • php中Session使用方法详解

    php中Session使用方法详解

    2021年10月23日
  • origin绘图软件安装包及入门使用

    origin绘图软件安装包及入门使用1、安装包(2018版)origin是大多被数科研人员选择的数据绘图软件,功能齐全,简单易用,百度云:链接:https://pan.baidu.com/s/1fQRtfwczwye8MfPDi6BmrQ提取码:y72a安装过程及破解方法比较简单自行搜索2、软件界面介绍打开软件如下图所示,1、book用来存放实验数据,如果有多个Y值可以点击工具栏中“列”来添加更多的列值。表格中的数据可以直接从excle中复制进来,简单易用。2、绘图:在book中加入数据后,选中数据选择左下…

  • lib vs 生成pdb_pdb文件 VS c++编译[通俗易懂]

    lib vs 生成pdb_pdb文件 VS c++编译[通俗易懂]使用VS-debug模式下编译的时候,经常出现以下问题:’Dlib.exe'(Win32):Loaded’D:\c++\Dlib\x64\Debug\Dlib.exe’.Symbolsloaded.’Dlib.exe'(Win32):Loaded’C:\Windows\System32\ntdll.dll’.CannotfindoropenthePDBfile.’Dl…

  • JS数组合并(5种)[通俗易懂]

    JS数组合并(5种)[通俗易懂]前言项目过程中,经常会遇到JS数组合并的情况,时常为这个纠结。这里整理一下。简单而实用的for最容易想到的莫过于for了。会变更原数组,当然也可以写成生成新数组的形式。letarr=[1,2]letarr2=[3,4]for(letiinarr2){arr.push(arr2[i])}console.log(arr)//[1,2,3,4]arr.concat(arr2)会生成新的数组。letarr=[1,2]let

发表回复

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

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