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.
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.
---------------------------------------------------------分界线------------------------------------------------------------------------
由题目描述可知：
该题 典型的拓扑排序。
1、在 拓扑排序时，当出现同时可访问两个节点或多个节点时，则信息不完全。
2、当出现有环时，则有冲突，判断是否有环可以在拓扑排序完时判断是否有点未访问。因为若无环，每个点都可以访问。
不多说了，附上我的AC代码：
1 #include <queue> 2 #include <cstdio> 3 #include <cstring> 4 #include <iostream> 5 using namespace std; 6 const int MAXN=2500; 7 int n,m,cas,id; 8 9 struct edge 10 { 11 int v,nx; 12 }set[MAXN]; 13 int head[30],d[30],ok[30],write[30]; 14 queue<int> Q; 15 16 void Addedge(int u,int v) 17 { 18 id++;set[id].v=v;set[id].nx=head[u]; 19 head[u]=id; 20 } 21 22 int bfs() 23 { 24 cas=0; 25 while(!Q.empty())Q.pop(); 26 int out=1,t,u;t=0; 27 for(int i=1;i<=n;i++) 28 if(!ok[i]) 29 { 30 t++;Q.push(i); 31 } 32 if(t>1)out=0; 33 while(!Q.empty()) 34 { 35 u=Q.front();Q.pop();t=0;write[++cas]=u; 36 for(int k=head[u];k>0;k=set[k].nx) 37 { 38 ok[set[k].v]--; 39 if(!ok[set[k].v]) 40 { 41 t++;Q.push(set[k].v); 42 } 43 } 44 if(t>1)out=0; 45 } 46 for(int i=1;i<=n;i++)if(ok[i]>0){out=-1;break;} 47 return out; 48 } 49 50 char print() 51 { 52 for(int i=1;i<=cas;i++)printf("%c",(char)(write[i]+64)); 53 return '.'; 54 } 55 56 int main() 57 { 58 while(~scanf("%d%d",&n,&m)) 59 { 60 memset(write,0,sizeof(write)); 61 memset(d,0,sizeof(d)); 62 memset(head,-1,sizeof(head)); 63 id=0; 64 int now=0,loca; 65 char a,b,c; 66 if(n==0 && m==0)break; 67 for(int i=1;i<=m;i++) 68 { 69 cin>>a>>b>>c; 70 if(b=='<') 71 { 72 Addedge(a-64,c-64);d[c-64]++; 73 } 74 else 75 { 76 Addedge(c-64,a-64);d[a-64]++; 77 } 78 if(now==0) 79 { 80 for(int j=1;j<=n;j++)ok[j]=d[j]; 81 now=bfs();loca=i; 82 } 83 } 84 if(now==0)puts("Sorted sequence cannot be determined."); 85 else if(now==1)printf("Sorted sequence determined after %d relations: ",loca),printf("%c\n",print()); 86 else printf("Inconsistency found after %d relations.\n",loca); 87 } 88 return 0; 89 }
记得点赞欧。