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.

输入样例

4 6
A A B C B A 3 2
A B 26 1
A 0 0

输出样例
Sorted sequence determined after 4 relations: ABCD.

Inconsistency found after 2 relations.

Sorted sequence cannot be determined.

我们现在只看样例：4和6的含义分别是：

4表示表达式中一共含有4个字符，也就是说我们需要排序的是4个样例，6呢，就是需要用户输入6个表达式，我们根据这两个数值和相应的表达式，去推算字符的先后顺序

，可能会有三种结果，一种当然是排序成功，比如第一个输入，一种是会有逻辑冲突，比如第二个输入，一种就是条件不足，不能判断

我的算法思想是这样的，定义一个结构体，该结构体有三个变量，一个是key表示字符，一个是value，表示权重，一个就是布尔变量，表示该值是否已经参加运算

1.根据用户输入初始换结构体数组变量（chain_head），将相应的key值存到结构体当中，value则是UNSET，布尔类型变量则是false，表示还未参加到运算当中，

2.接下来，计算第n个表达式（n初始化成0），我们获取第n个表达式的第一个和第三个字符，分别获得该key在结构体数组中的索引，index_a和index_b，这样需要比较的就是

chain_head[index_a]和chain_head[index_b]了，首先看下chain_head[index_a].value是否小于chain_head[index_b].value,如果小于，则不进行任何操作，继续计算第n+1个

表达式，如果chain_head[index_a].value大于chain_head[index_b].value并且，chain_head[index_b].FirstApper=true(index_b的结构体从未参加运算)，则表示逻辑冲突，停

止循环，输出结构，如果chain_head[index_a].value==chain_head[index_b].value则chain_head[index_b].value=chain_head[index_a].value+1;即可，然后进行第n+1个表达

式的计算，继续进行第二步的运算

3.清理现场，输出结果

源代码如下：

// Sort_It.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include
using namespace std;
/****************************************************************************************************************
***文件名称：Sort_It.cpp
***文件描述：根据表达式对字符进行排序
****************************************************************************************************************/
typedef struct {
	char key;
	int value;	
	bool FirstApper;
}Key_Value;
Key_Value* chain_head=NULL;
int  nCount=0;//需要排序的字符个数
int  nCur_Count=0;//当前已经赋值的个数
int result=0;
#define DONE  1
#define INCONSIST 2
#define UNENOUGH 3
#define UNSET  1
void operation(char key_a,char key_b);
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///函数名称：TestOver
///函数描述：检测根据当前获得信息，检测是否已经可以完成排序（value的值叠加，如果等于1,2,3的和则表示排序完成）
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////
bool TestOver(Key_Value* head)
{
	int nSum_1=0,nSum=0;
	for(int i=0;ichain_head[index_b].value&&(chain_head[index_b].FirstApper==false||chain_head[index_a].FirstApper==false))
	{
		//违反逻辑
		result=INCONSIST;
	}
	else
	{
		//重新赋值
		chain_head[index_b].value=chain_head[index_a].value+1;		
		chain_head[index_b].FirstApper=false;
		chain_head[index_a].FirstApper=false;
	}
}
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///函数结束
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////


/////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///函数名称：struct_init
///函数名称：根据用户输入将信息转换成我们需要操作的几种结构体
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////
void struct_init(char**strChar,int nRelationsLen)
{
	//开始向里面赋值
	bool mark=false;
	int nCur=0;
	for(int i=0;i>nCount;
	cin>>nRelationsLen;
	chain_head=new Key_Value[nCount];
	char **strChar=NULL;
	strChar=new char*[nCount];	
	for(int i=0;i>strChar[i];		
	}
	char* str_output=NULL;
	struct_init(strChar,nRelationsLen);
	for(int i=0;i