poj 1094 Sorting It All Out(nyoj 349)

时间:2023-01-18 10:51:15

点击打开链接

Sorting It All Out
Time Limit: 1000MS   Memory Limit: 10000K
Total Submissions: 24544   Accepted: 8503

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.

题目大意是:给出若干个关系,判断是否能判断出各个数的顺序,如果能,那么输出再第几个关系的时候就能确定顺序,如果不能,有两种输出,要么出现矛盾,要么直到所有关系都判断完了也没法确定顺序

使用拓扑排序每次去掉一个入度为0的点

#include<stdio.h>
bool map[27][27];
char str[27];
int tuopu(int total)
{
bool flag[27] = {0};
int count = 0;
int inagree = 0;
int i, j;
int f;
int n = 0;
int ex;
int mark;
bool ex_flag = 0;
for(ex = 0; ex < total; ex++)
{
inagree = 0; for(i = 0; i < total; i++)
{
f = 0;
if(flag[i] == 1)
continue;
for(j = 0; j < total; j++)
{
if(map[j][i] == 1 && flag[j] == 0)
{
f = 1;
break;
}
}
if(f == 0)
{
inagree++;
mark = i;
}
if(inagree > 1)
{
ex_flag = 1;
break;
}
}
if(inagree == 0 && count < total)
{
return -1;
}
flag[mark] = 1;
count ++;
str[n ++] = 'A' + mark;
}
if(ex_flag == 1)
return 1;
str[n] = 0;
return 0;
}
int main()
{
int n, m;
while(scanf("%d %d", &n, &m), n != 0 || m != 0)
{
getchar();
int i;
char a, b;
int flag = 1;
int mark;
for(i = 1; i <= m; i++)
{
scanf("%c<%c", &a, &b);
getchar();
if(flag != -1 && flag != 0)
{
map[a - 'A'][b - 'A'] = 1;
int temp = tuopu(n);
if(temp == 0)
{
flag = 0;//成功
mark = i;
}
else if(temp == -1)
{
flag = -1;//矛盾
mark = i;
}
}
}
if(flag == 0)
printf("Sorted sequence determined after %d relations: %s.\n", mark, str);
else if(flag == 1)
printf("Sorted sequence cannot be determined.\n");
else
printf("Inconsistency found after %d relations.\n", mark);
int j;
for(i = 0; i < 27; i++)
{
for(j = 0; j < 27; j++)
map[i][j] = 0;
}
}
return 0;
}

poj 1094 Sorting It All Out(nyoj 349)的更多相关文章

  1. &lbrack;ACM&rsqb; POJ 1094 Sorting It All Out (拓扑排序)

    Sorting It All Out Time Limit: 1000MS   Memory Limit: 10000K Total Submissions: 26801   Accepted: 92 ...

  2. POJ - 1094 Sorting It All Out(拓扑排序)

    https://vjudge.net/problem/POJ-1094 题意 对于N个大写字母,给定它们的一些关系,要求判断出经过多少个关系之后可以确定它们的排序或者排序存在冲突,或者所有的偏序关系用 ...

  3. 题解报告:poj 1094 Sorting It All Out(拓扑排序)

    Description An ascending sorted sequence of distinct values is one in which some form of a less-than ...

  4. poj&period;1094&period;Sorting It All Out(topo&rpar;

    Sorting It All Out Time Limit: 1000MS   Memory Limit: 10000K Total Submissions: 28762   Accepted: 99 ...

  5. 【POJ】1094 Sorting It All Out(拓扑排序)

    http://poj.org/problem?id=1094 原来拓扑序可以这样做,原来一直sb的用白书上说的dfs............ 拓扑序只要每次将入度为0的点加入栈,然后每次拓展维护入度即 ...

  6. POJ 1094 Sorting It All Out(经典拓扑&plus;邻接矩阵)

    ( ̄▽ ̄)" //判环:当入度为0的顶点==0时,则有环(inconsistency) //判序:当入度为0的顶点仅为1时,则能得到有序的拓扑排序,否则无序 //边输入边判断,用contin ...

  7. POJ 1094 Sorting It All Out(拓扑排序&plus;判环&plus;拓扑路径唯一性确定)

    Sorting It All Out Time Limit: 1000MS   Memory Limit: 10000K Total Submissions: 39602   Accepted: 13 ...

  8. POJ 1094 Sorting It All Out (拓扑排序,判断序列是否唯一,图是否有环)

    题意:给出n个字符,m对关系,让你输出三种情况:     1.若到第k行时,能判断出唯一的拓扑序列,则输出:         Sorted sequence determined after k re ...

  9. ACM&colon; poj 1094 Sorting It All Out - 拓扑排序

    poj 1094 Sorting It All Out Time Limit:1000MS     Memory Limit:10000KB     64bit IO Format:%lld &amp ...

随机推荐

  1. gvim设置成不备份文件

    打开gVim,进入“编辑”-“启动设定” 在“behave mswin”下行位置添加 set nobackup 语句 退出并保存配置文件 :wq

  2. Java 中String常用方法

    java中String的常用方法 1.length() 字符串的长度 例:char chars[]={'a','b'.'c'}; String s=new String(chars); int len ...

  3. java&lowbar;jdbc&lowbar;可变参数&lowbar;MetaData

    异常处理参考3层解耦 ublic class ScrollTest { public static void main(String[] args) throws SQLException { // ...

  4. javascript学习-对象与原型

    javascript学习-对象与原型 Javascript语言是符合面向对象思想的.一般来说,面向对象思想需要满足以下三个基本要求: 封装,Javascript的对象可以*的扩充成员变量和方法,自然 ...

  5. centos7安装httpd和php

    centos7许多命令都变了,又要重新记了. centos7默认安装了httpd吧?记不清了,看一下: rpm -qa |grep httpd 没有的话,安装一下吧. yum -y install h ...

  6. &lbrack;asp&period;net mvc 奇淫巧技&rsqb; 03 - 枚举特性扩展解决枚举命名问题和支持HtmlHelper

    一.需求 我们在开发中经常会遇到一些枚举,而且这些枚举类型可能会在表单中的下拉中,或者单选按钮中会用到等. 这样用是没问题的,但是用过的人都知道一个问题,就是枚举的命名问题,当然有很多人枚举直接中文命 ...

  7. GDAL1&period;11版本对SHP文件索引加速测试

    GDAL库中对于矢量数据的读取中可以设置一些过滤器来对矢量图形进行筛选,对于Shapefile格式来说,如果数据量太大,设置这个过滤器时间慢的简直无法忍受.好在GDAL1.10版本开始支持读取Shap ...

  8. coercing to Unicode&colon; need string or buffer&comma; int found报错

    转为string类型 str(a)

  9. Confluence 6 删除和归档空间

    我们希望你已经成功的完成了这个任务,同时还学习到了一些有关 Confluence 空间的多样性和强大的功能.后推到 18 个月以后,我们来看看你的火星移民计划进行的怎么样了. 如果你希望删除老的空间( ...

  10. Tinyos学习笔记(三)

    读取Telosb内部传感器数据,并在计算机上显示. senseC.nc代码如下: #include "Timer.h" #include "sense.h" # ...