Sorting It All Out（拓扑排序）

K - Sorting It All Out

Crawling in process... Crawling failed Time Limit:1000MS     Memory Limit:10000KB     64bit IO Format:%I64d & %I64u

Submit Status

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.

      题意：

      有N个对象和M对关系，根据这M对关系判断是否能排成一个确定的序列。

      思路：

      拓扑排序，用邻接矩阵表示，另外开一个数组存每个顶点的入度，每次判断出入度为0的顶点后加入新的数组中，删除该顶点，同时与之相邻的顶点入度分别-1，重复以上步骤直到所有顶点都放入到新的数组中。但是本题还有个隐含条件，每输入一对关系，如果判定有结果，则可以忽略后面输入数据，即使后面输入数据能改变结果，也不用管。所以应该每输入一个关系就去更新当前的图，然后进行一趟拓扑排序。一旦产生结果，再对后面的数据处理下，就可以输出结果。

 AC:

 

#include<stdio.h>
#include<string.h>
int n,m,time,time1,time2;
int temp,number,test,number2,test2;
int map[50][50],degree[50],match[50];
int sort[50],end[50];
void topo()
{
	int in,k;
	memset(sort,0,sizeof(sort));
	for(int i=0;i<n;i++)
	match[i]=degree[i];
//每次都把入度数组复制在match数组中，再对match进行判断
	k=0;
	while(k<n)
	{
	number=0;
	number2=0;
	for(int i=0;i<n;i++)
	   {
	    if(!match[i])  
	      {in=i;number++;}
//number是用来判断里面有多少个入度为0的顶点
	    if(match[i]==-1) number2++;
//number2是用来判断是否出现了条件2的情况的
//有点乱来，这是不满意的地方
//因为这只是针对最后一次排序时候，出现match数组全部变成-1的情况
//全为-1说明已经全部排好序了
//如果有环的话，说明这时候match没有值为0的一项
//而排好序的话，全变成-1了，数组match里面任何一项也不会出现0
//所以会一直记录time2的时间为0
	   }
	    if(number2!=n&&!number)  test2=1;
//如果number等于0且number2不等于n，才能说明在排序的时候没有入度为0的一项
	    if(number>1)             test=1;
//test是用来判断某次排序的时候，是否曾经出现过有环的情况
	    sort[k++]=in;
//找到这个入度为0的顶点，放在sort中
	    match[in]=-1;
//-1表示已经删除了这个顶点
	    for(int i=0;i<n;i++)
	       if(map[in][i]>0)  match[i]--;
//遍历矩阵，找相邻顶点后入度-1
	}		
}

int main()
{
	int k;
	char task[5];
	while(scanf("%d%d",&n,&m)&&(n||m))
//n和m可以有其中一个为0的情况
	{
		temp=0;
//temp判断是三种情况中的哪一个
		time1=0;
//time1记录第一次完成排序的时间
    	        time2=0;
//time2记录第一次出现矛盾排序的时间
		memset(map,0,sizeof(map));
		memset(degree,-1,sizeof(degree));
		for(time=0;time<m;time++)
		 {
			 int x,y;
			 scanf("%s",task);
		 	 x=task[0]-'A';
		 	 y=task[2]-'A';
//如果不加判断条件！map[x][y]的话，对于两次输入都一样的情况则会使某项入度+1
			 if(!map[x][y])
			 {
			   if(degree[x]==-1) degree[x]=0;
			   if(degree[y]==-1) degree[y]=1;
			   else degree[y]++;
		         }
			   map[x][y]=1;
//判断后标记这个点为1
			   if(map[x][y]==1&&map[y][x]==1&&!temp)
		 	     {
		 	 	time2=time;
		 	 	temp=2;
		 	     }
//其实这个条件是可以忽略的，因为一开始理解错了
//这个地方需要改进，很不满意
			  test=0;
			  test2=0;
			  topo();
			  if(test2&&!temp)
			  {
			  	time2=time;
			  	temp=2;
			  }
			  k=0;
			  for(int i=1;i<n;i++)
		 	     if(sort[i]!=sort[i-1])  k++;
		 	     else break;	
//判断这个时候的sort序列是不是全部都是不一样的数，如果有一样的话说明还没排好序
//其实这个条件也是错误的，因为一开始写的时候没考虑清楚，后来要改动的话又会牵扯很多东西
//所以就一直放着了，这也是很不满意的地方
			 if(!test&&!temp&&k==n-1)
		 	 {
		 	 	time1=time;
		 	 	temp=1;
                                for(int i=0;i<n;i++)
                                end[i]=sort[i];
//第一次排好序的时候把sort复制到end中
//因为可能不是最后一次才排好序，不是最后一次的话sort会一直变
//所以应该第一次排好的时候就复制到end中
		 	 }
		 }		 		 
		if(!n)
		{
		   printf("Sorted sequence determined after 1 relations: .\n");	
		}
//这也只是针对n等于0时候的情况的，这又是一个不满意的地方
		if(n)
	        {
		  if((time1<time2&&time2&&temp==1)||(time1&&!time2&&temp==1)||(time1==0&&temp==1))
		      {
			printf("Sorted sequence determined after %d relations: ",time1+1);
			for(int i=0;i<n;i++)
			   printf("%c",end[i]+'A');
			printf(".\n");
		      }
		  if((time2<time1&&time1&&temp==2)||(time2&&!time1&&temp==2)||(time2==0&&temp==2))  
		        printf("Inconsistency found after %d relations.\n",time2+1);
		  if(!temp)  
		        printf("Sorted sequence cannot be determined.\n");
//三项判断输出，肯定有简便的地方
//一开始写觉得非常繁杂啰嗦，这也是不满意的地方
	        }
       }
}

    总结：

 

    一开始并不知道题目有这个隐含条件，所以理解方面很曲折。理解了之后，敲代码的时候也非常的混乱，之后一定要抽时间再理清一遍，再认真思考后写一遍。除此之外，还需用邻接表，DFS的方法写一遍。WA很多次，后来发现错误竟然是输出句子中的其中一个单词少了个s……所以以后首先应该检查输出语句有没有错误先，代码写得很不满意，写得非常不好，过后还需要更新一次。学习一个新的算法很快，但是要运用起来真的需要很多时间，自己写的代码真的很没通用性，只针对某些条件然后再逐条加上去，这是因为思路还没很清晰造成的。