题目

链接

http://poj.org/problem?id=1094

字面描述

Sorting It All Out
Time Limit: 1000MS Memory Limit: 10000K
Total Submissions: 46761 Accepted: 16219
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 A B C B A 3 2
A B 26 1
A 0 0
Sample Output

Sorted sequence determined after 4 relations: ABCD.
Inconsistency found after 2 relations.
Sorted sequence cannot be determined.
Source

East Central North America 2001

思路

1. 无序：入度点数为0的点数大于1
2. 有环：开始没有入度为0的点||最终没有遍历完
3. 有序：上述条件之外

重点

$有环的优先级大于无序的优先级$

代码实现

#include
#include
#include
#include
using namespace std;

const int maxn=100+10;
int n,m;
int indegree[maxn],topo[maxn],indegree1[maxn];
bool map[maxn][maxn];
inline int Topo_sort(int n){
	stack<int>s;
	int cnt=0,cnt0=0,flag1=1;
	for(int i=1;i<=n;i++)indegree1[i]=indegree[i];
	for(int i=1;i<=n;i++){
		if(indegree1[i]==0){
			s.push(i);
			cnt0++;
		}
	}
	if(cnt0==0)return 2;
	if(cnt0>1)flag1=0;
	while(!s.empty()){
		cnt0=0;
		int u=s.top();
		s.pop();
		topo[++cnt]=u;
		for(int i=1;i<=n;i++){
			if(map[u][i]){
				if(--indegree1[i]==0){
					s.push(i);
					cnt0++;
				}
			}
		}
		if(cnt0>1)flag1=0;
	}
	if(cnt<n)return 2;
	return flag1;
}
int main(){
	//freopen("1094.in","r",stdin);
	//freopen("1094.out","w",stdout);
	while(1){
		scanf("%d%d",&n,&m);
		if(!n&&!m)break;
		memset(indegree,0,sizeof(indegree));
		memset(map,false,sizeof(map));
		//memset(vis,false,sizeof(vis));
		int flag=0;
		for(int i=1;i<=m;i++){
			char x,y,z;
			scanf(" %c %c %c",&x,&y,&z);
			if(flag)continue;
			indegree[z-64]++;
			map[x-64][z-64]=true;
			//vis[x-64]=true;
			//vis[z-64]=true;
			//printf("%d ",indegree[z-64]);
			int op=Topo_sort(n);
			//printf("%d ",op);
			if(op==2){
				printf("Inconsistency found after %d relations.\n",i);
				flag=1;
				continue;
			}
			else if(op==1){
				printf("Sorted sequence determined after %d relations: ",i);
				for(int j=1;j<=n;j++)printf("%c",topo[j]+64);
				printf(".\n");
				flag=1;
				continue;
			}
			//printf("%d ",flag);
		}
		if(!flag)printf("Sorted sequence cannot be determined.\n");
		//for(int i=1;i<=n;i++)printf("%d ",indegree[i]);
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80

极端测试样例一组

15 60
B M N N I B A O D F I F I C I I A B G A N H K K F C K G F M A B E B F M M N O D O B A I F C A N A F K C O I D I F M H N Inconsistency found after 48 relations.