Sorting It All Out
| Time Limit: 1000MS | Memory Limit: 10000K | |
| Total Submissions: 29744 | Accepted: 10293 |
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
代码
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;
int map[100][100];
int m,n;
int tindegree[100],indegree[100];
char str[5];
char s[39];
int toposort(){
bool flag=true;
memset(tindegree,0,sizeof(tindegree));
memset(s,0,sizeof(s));
for(int i=1;i<=n;i++){
tindegree[i]=indegree[i];
}
for(int i=1;i<=n;i++){
int sum=0,k;
for(int j=1;j<=n;j++){
if(!tindegree[j]){
k=j;
sum++;
}
}
if(sum==0){///入度为0，则所剩图为一个环，无法判断了。直接可以返回，
return -1;
}
if(sum>1){///当出现入度为0的点有多个时候，可能判断不了，但是也不能直接返回0，因为带环循环会优先于
///无法判断这种情况，所以需要继续执行该函数，看还有没有死循环为环的情况
flag=false;
}
s[i-1]=k+'A'-1;
tindegree[k]--;
for(int z=1;z<=n;z++){
if(map[k][z]){
tindegree[z]--;
}
} }
s[n]='\0';///s字符串结束标志
if(flag==false)
return 0;
return 1;
}
int main(){
while(scanf("%d%d",&n,&m)!=EOF){
if(n==0&&m==0)
break;
memset(map,0,sizeof(map));
memset(indegree,0,sizeof(indegree));
memset(str,0,sizeof(str));
memset(s,0,sizeof(s));
int ans=2;
int temp;
bool flag=true;
for(int i=1;i<=m;i++){
scanf("%s",str);
if(flag==false)
continue;
int u=str[0]-'A'+1;
int v=str[2]-'A'+1;
if(!map[u][v]){
map[u][v]=1;
indegree[v]++;
}
ans=toposort();
if(ans==-1||ans==1){///此判断语句特别注意，只能记录状态，不能退出，需要继续读边
temp=i;
flag=false;
}
}
if(ans==1)
printf("Sorted sequence determined after %d relations: %s.\n",temp,s);
else if(ans==-1)
printf("Inconsistency found after %d relations.\n",temp);
else if(ans==2)
printf("Sorted sequence cannot be determined.\n"); }
return 0;
}