poj 1094 Sorting It All Out （拓扑排序） - c++编程基础

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