POJ1094Sorting It All Out题解

题目

链接

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<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.
Source

East Central North America 2001

思路

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

重点

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

代码实现

#include<cstdio>
#include<cstring>
#include<string.h>
#include<stack>
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;
}

极端测试样例一组

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