Sorting It All Out
| Time Limit: 1000MS |
|
Memory Limit: 10000K |
| Total Submissions: 27929 |
|
Accepted: 9655 |
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
Sample Output
Sorted sequence determined after 4 relations: ABCD.
Inconsistency found after 2 relations.
Sorted sequence cannot be determined.
思路：根据矛盾优先原则，即只要出现矛盾就结束程序，输出答案；然后再没有矛盾的基础上进行拓扑排序看能否得出它们之间关系；最后，若以上两者均没有结果，则是条件不足。同时，我们要输入一个关系进行一次判断。
在程序中，每次拓扑后若满足合法的拓扑条件，就记录答案。最后判断是否有矛盾关系即可。
#include"stdio.h"
#include"string.h"
#include"vector"
#include"queue"
#include"iostream"
#include"algorithm"
using namespace std;
#define N 1000
#define M 26
vector
g[M]; //记录拓扑关系
int pre[M],n,m,flag,t;
int mark[M]; 标记字符是否出现及是否使用过
char ans[M+5]; 记录答案
void top_sort(int k)
{
t=k+1;
int i,j,u,v,tmp;
queue
q; memset(pre,0,sizeof(pre)); memset(mark,0,sizeof(mark)); for(i=0;i
0) //出现该情况肯定是出现矛盾 flag=2; else if(j==n) flag=1; ans[j]='\0'; } int main() { char s[10]; int i,u,v; while(scanf("%d%d",&n,&m),n||m) { flag=0; for(i=0;i