這道題目考察了拓撲排序的基本思想：每一步尋找一個入度為0的結點，然后 刪除之。將這個結點指向的結點入度減1。刪除從這個結點出發的所有邊

同時考察了對于一個有向圖是否有環、是否嚴格有序的判斷。（當發現多個結點的度 為0時，則不是嚴格有序。當發現沒有結點入度為0時，則有環） 需要注意的是邏輯上的關系。“Sorted sequence cannot be determined.”這個判斷， 要放在最后，即只有發現了所有的點都沒有環，且并沒有發現嚴格有序性質的時候， 才可以判為“Sorted sequence cannot be determined."邏輯上的判決一定要注意優先級。

這個問題中優先級最高的是判斷有環。一旦發現找不到度為0的結點，則立即return。

第二優先級是是否嚴格有序的判斷。當每一步能且只能找到一個度為0的結點，則return。

第三優先級是無法確定。(當發現無法確定時，并不能立即return，因為還需要判斷是否有環）

思維方式:當條件x成立時，另外的條件y，z是否一定不成立。如果一定不成立， 則可以斷言return。否則必須繼續判斷下去。 提交記錄： 1.樣例未過！由于拓撲排序算法中，處理過程中入度減1的同時，并沒有將對應的邊刪掉。 2.樣例未過！ 由于在子函數judge中，對graph圖進行了修改，導致后面處理失敗。增加了memcpy解決。 4.wrong answer！ 在judge函數中，當出現多個結點度為0的時候，還需要繼續判沖突，而不能直接return

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. #include<cstdio> #include<string.h> #include<algorithm> using namespace std; int ans,m,n; char top[50]; int s[50],t[50];//t數組記錄v贏了幾次,s數組保留贏的次數 int book[50][50]; int mark[30]; int tuopu() {int l=0,flag=0;for(int h=1; h<=ans; h++){int k=-1,num=0;for(int i=1; i<=n; i++){if(mark[i]&&s[i]==0)//字母出現過,但是一次也沒贏{k=i;num++;}}if(k==-1)return -1;if(num!=1)flag=1;s[k]=-1;top[l]='A'+(k-1);l++;for(int i=1; i<=n; i++){if(book[k][i])s[i]--;}}top[l]=0;if(ans==n&&flag==0)return 1;return 0; } int main() {while(~scanf("%d%d",&n,&m)&&(n+m))//n個字母,m組關系{ans=0;int flag=0;char c[10];memset(t,0,sizeof(t));memset(mark,0,sizeof(mark));//標記字母是否出現過memset(book,0,sizeof(book));for(int i=1; i<=m; i++){scanf("%s",c);if(flag==1)//已找到目標情況continue;int u=c[0]-'A'+1;int v=c[2]-'A'+1;if(mark[u]==0){mark[u]=1;ans++;}if(mark[v]==0){mark[v]=1;ans++;}if(book[u][v]==0){t[v]++;book[u][v]=1;for(int j=0; j<30; j++)s[j]=t[j];//將贏的次數保留下來int a=tuopu();if(a==-1)//有環{printf("Inconsistency found after %d relations.\n",i);flag=1;}else if(a==1)//有序{printf("Sorted sequence determined after %d relations: %s.\n",i,top);flag=1;}}}if(flag==0)printf("Sorted sequence cannot be determined.\n");}return 0; }

?

總結

以上是生活随笔為你收集整理的Sorting It All Out （易错题+拓扑排序+有向图（判环+判有序）优先级）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。