| Time Limit: 1000MS | Memory Limit: 10000K | |
| Total Submissions: 26866 | Accepted: 9267 |
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.
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.
要看清题。
。。。
Sorted sequence determined after 4 relations: ABCD. 输入前4个关系后，决定出了一个序列（关系总数可能大于4） Inconsistency found after 2 relations. 输入前2个关系后，冲突出现了（环，关系总数可能大于2） Sorted sequence cannot be determined. 全部关系输入后。序列和冲突均无出现
偏序与全序：
从离散数学的角度来看，拓扑排序就是由某集合上的一个偏序得到该集合上的一个全序。
直观的来说，偏序即集合中仅部分元素间可比較（存在某些元素间无法比較）。全序即集合中全部元素间均可比較。
更直观地。一个偏序能够是一个流程图，表示完毕某项任务过程中各个步骤之间的次序关系，拓扑排序的任务是在这个偏序上得到一个全序，即得到一个完毕整个项目的各步骤的序列。
排序依赖的原则就是各个步骤之间的优先关系。
拓扑排序得到的序列不一定是唯一的，由于某些步骤间没有规定优先关系（这就是偏序的特点），在拓扑排序的时候人为的增加一些规则，使得到的序列为满足偏序关系的一个全序。
用一个有向无环图更加有助于理解。
#include<cstdio>
#include<iostream>
#include<cstring>
#include<queue>
#include<algorithm>
#include<vector>
using namespace std;
const int M = 30 ;
const int N = 1000 + 50;
int n, m;
char inchar[N][M];
char outchar[M];
int in[M];
int cut;
vector<int>amap[M];
int flag;
int toposort()
{
cut = 0;
queue<int>que;
int temp[M];
memcpy( temp, in, sizeof( in ) );
bool all_out = true; //是否是全序的标记
for( int i=0; i<n; i++ )
if( !temp[i] )
que.push( i );
while( !que.empty() )
{
if( que.size()>1 ) //若队列里不是一个元素时。就不是全序的了
all_out = false;
int a = que.front();
que.pop();
outchar[ cut++ ] = a + 'A';
for( int i=0; i<amap[a].size(); i++ )
{
int b = amap[a][i];
if( --temp[b]==0 ) //若元素多次出现， 则先不进队
que.push( b );
}
}
if( cut<n )
return -1; //cut<n， 说明存在环。冲突
else if( all_out==true )
return 1;
else
return 0;
}
int main()
{
while( scanf( "%d%d", &n, &m )==2 &&n &&m )
{
memset( in, 0, sizeof( in ) );
for( int i=0; i<n; i++ )
amap[i].clear();
for( int i=0; i<m; i++ )
scanf( "%s", inchar[i] );
flag = 0;
int cas;
for( cas=0; cas<m; cas++ )
{
int a = inchar[cas][0] - 'A';
int b = inchar[cas][2] - 'A';
amap[a].push_back( b );
in[b]++;
flag = toposort();
if( flag!=0 )
break;
}
outchar[n] = ' '; // 注意在输出的数据后加个结束符
if(flag==1) printf("Sorted sequence determined after %d relations: %s.
", cas+1, outchar);
else if(flag==0) printf("Sorted sequence cannot be determined.
");
else if(flag==-1) printf("Inconsistency found after %d relations.
", cas+1);
}
return 0;
}