输入数据：

4 6

A

A

B

C

B

A

3 2

A

B

26 1

A

0 0

Sorted sequence determined after 4 relations: ABCD.(4组出现后就能确定)

Inconsistency found after 2 relations.(两组出现后发现有环)

Sorted sequence cannot be determined.（不能确定，有多种可能）

1. /*  
2.  * TopSortDemo.cpp  
3.  *  
4.  * Created on: 2012-6-17  
5.  *      Author: Administrator  
6.  */ 
7. #include<stdio.h>  
8. #include<string.h>  
9. #define M 100  
10. struct ArcNode{  
11.     int to;  
12.     struct ArcNode *next;  
13. };  
14. ArcNode *List[M];//表示图  
15. int counts[M];//表示顶点的入度 //同时，也充当了栈的作用  
16. char output[M];  
17. int n,m;//边和顶点  
18.    
19. void topSort(){  
20.     //把入度为零的顶点入栈  
21.     int top=-1;  
22.     for(int i=0;i<n;++i){  
23.        if(counts[i]==0){  
24.            counts[i]=top;  
25.            top=i;  
26.        }  
27.     }  
28.    
29.     bool bcycle=false;  
30.     int pos=0;  
31.     ArcNode *temp;  
32.     for(int i=0;i<n;++i){  
33.    
34.        if(top==-1){
    //如果在顶点没有处理完之前，没有入度为零的顶点，则说明有环  
35.            bcycle=true;  
36.            break;  
37.        }else{  
38.    
39.            int j=top;top=counts[top];//取出顶点  
40.    
41.            pos+=sprintf(output+pos,"%d ",j+1);//把顶点输出到output数组中  
42.    
43.            //把与顶点相邻顶点的入度减1  
44.            temp=List[j];  
45.            while(temp!=NULL){  
46.               int k=temp->to;  
47.               --counts[k];  
48.    
49.               if(counts[k]==0){
    //如果顶点的入度减少到零，则入栈  
50.                   counts[k]=top;top=k;  
51.               }  
52.               temp=temp->next;  
53.            }  
54.        }  
55.     }  
56.     //最后把结果输出  
57.     if(bcycle){  
58.        printf("Network has a cycle!\n");  
59.     }else{  
60.        int len=strlen(output);  
61.        output[len-1]=0;  
62.        printf("%s\n",output);  
63.     }  
64. }  
65. int main(){  
66.     while(1){  
67.        scanf("%d%d",&n,&m);//输入点数和边数  
68.        if(n==0&&m==0)break;  
69.    
70.        memset(List,0,sizeof(List));  
71.        memset(counts,0,sizeof(counts));  
72.        memset(output,0,sizeof(output));  
73.    
74.        ArcNode *temp;  
75.        int v,u;  
76.        for(int i=0;i<m;++i){  
77.            scanf("%d%d",&v,&u);//输入一条边  
78.            --v;--u;  
79.            ++counts[u];  
80.    
81.            temp=new ArcNode;  
82.            temp->to=u;  
83.            temp->next=NULL;  
84.    
85.            if(temp==NULL){  
86.               List[v]=temp;  
87.            }else{  
88.               temp->next=List[v];  
89.               List[v]=temp;  
90.            }  
91.        }  
92.        //拓扑排序  
93.        topSort();  
94.    
95.        //收回内存  
96.        for(int i=0;i<n;++i){  
97.            temp=List[i];  
98.            while(temp=NULL){  
99.               List[i]=temp->next;  
100.               delete temp;  
101.               temp=List[i];  
102.            }  
103.        }  
104.     }  
105.     return 0;  
106. }  

1. /*  
2.  * TopSortDemo.cpp  
3.  *  
4.  *  Created on: 2012-6-17  
5.  *      Author: Administrator  
6.  */ 
7. #include<stdio.h>  
8. #include<string.h>  
9. #include<stack>  
10. using namespace std;  
11. #define M 100  
12. struct ArcNode{  
13.     int to;  
14.     struct ArcNode *next;  
15. };  
16. ArcNode *List[M];//表示图  
17. int counts[M];//表示顶点的入度 //同时，也充当了栈的作用  
18. char output[M];  
19. int n,m;//边和顶点  
20. stack<int> S;  
21. void topSort(){  
22.     //把入度为零的顶点入栈  
23.  
24.     for(int i=0;i<n;++i){  
25.         if(counts[i]==0){  
26.             S.push(i);  
27.         }  
28.     }  
29.  
30.     bool bcycle=false;  
31.     int pos=0;  
32.     ArcNode *temp;  
33.     for(int i=0;i<n;++i){  
34.  
35.         if(S.empty()){
    //如果在顶点没有处理完之前，没有入度为零的顶点，则说明有环  
36.             bcycle=true;  
37.             break;  
38.         }else{  
39.  
40.             int j=S.top();S.pop();//取出顶点  
41.  
42.             pos+=sprintf(output+pos,"%d ",j+1);//把顶点输出到output数组中  
43.  
44.             //把与顶点相邻顶点的入度减1  
45.             temp=List[j];  
46.             while(temp!=NULL){  
47.                 int k=temp->to;  
48.                 --counts[k];  
49.  
50.                 if(counts[k]==0){
    //如果顶点的入度减少到零，则入栈  
51.                     S.push(k);  
52.                 }  
53.                 temp=temp->next;  
54.             }  
55.         }  
56.     }  
57.     //最后把结果输出  
58.     if(bcycle){  
59.         printf("Network has a cycle!\n");  
60.     }else{  
61.         int len=strlen(output);  
62.         output[len-1]=0;  
63.         printf("%s\n",output);  
64.     }  
65. }  
66. int main(){  
67.     while(1){  
68.         scanf("%d%d",&n,&m);//输入点数和边数  
69.         if(n==0&&m==0)break;  
70.  
71.         memset(List,0,sizeof(List));  
72.         memset(counts,0,sizeof(counts));  
73.         memset(output,0,sizeof(output));  
74.  
75.         ArcNode *temp;  
76.         int v,u;  
77.         for(int i=0;i<m;++i){  
78.             scanf("%d%d",&v,&u);//输入一条边  
79.             --v;--u;  
80.             ++counts[u];  
81.  
82.             temp=new ArcNode;  
83.             temp->to=u;  
84.             temp->next=NULL;  
85.  
86.             if(temp==NULL){  
87.                 List[v]=temp;  
88.             }else{  
89.                 temp->next=List[v];  
90.                 List[v]=temp;  
91.             }  
92.         }  
93.         //拓扑排序  
94.         topSort();  
95.  
96.         //收回内存  
97.         for(int i=0;i<n;++i){  
98.             temp=List[i];  
99.             while(temp=NULL){  
100.                 List[i]=temp->next;  
101.                 delete temp;  
102.                 temp=List[i];  
103.             }  
104.         }  
105.     }  
106.     return 0;  
107. }  

1. /*  
2.  * POJ_1094.cpp  
3.  *  
4.  * Created on: 2012-6-17  
5.  *      Author: Administrator  
6.  */ 
7. #include<stdio.h>  
8. #include<string.h>  
9. #include<algorithm>  
10. #include<queue>  
11. using namespace std;  
12. #define M 27  
13. struct ArcNode{  
14.     int to;  
15.     struct ArcNode *next;  
16. };  
17.    
18. ArcNode *List[M];  
19. int numbers[M];  
20. int cnumbers[M];//numbers的copy  
21. char output[M];  
22.    
23. char alph[M];  
24. char relation[4];//输入的关系  
25. int n,m;  
26. int topSort(int c){  
27.    
28.     copy(numbers,numbers+n,//source  
29.        cnumbers);//des  
30. // for(int i=0;i<n;i++)  
31. //         printf("%d\t",cnumbers[i]);  
32.     int top=-1;  
33.     ArcNode *temp;  
34.     int pos=0;  
35.     int zeros=0;  
36.     bool flag=true;  
37.     for(int i=0;i<n;++i){  
38.        if(cnumbers[i]==0){  
39.            cnumbers[i]=top;  
40.            top=i;  
41.            zeros++;  
42.        }  
43.     }  
44.     if(zeros>1)  
45.        flag=false;  
46.    
47.     while(c--){  
48.        zeros=0;  
49.        if(top==-1){  
50.            return -1;  
51.        }else{  
52.            int j=top;top=cnumbers[top];  
53.            output[pos++]=j+'A';  
54.            temp=List[j];  
55.            while(temp!=NULL){  
56.               int k=temp->to;  
57.               cnumbers[k]--;  
58.               if(cnumbers[k]==0){  
59.                   cnumbers[k]=top;top=k;  
60.                   zeros++;  
61.               }  
62.                temp=temp->next;  
63.            }  
64.            if(zeros>1){  
65.               flag=false;  
66.            }  
67.        }  
68.     }  
69.     if(flag)  
70.        return pos;  
71.     else 
72.        return 0;  
73. }  
74. int main(){  
75.     while(scanf("%d%d",&n,&m)!=EOF&&n!=0&&m!=0){  
76.    
77.        memset(List,0,sizeof(List));  
78.        memset(numbers,0,sizeof(numbers));  
79.        memset(output,0,sizeof(output));  
80.        memset(alph,0,sizeof(alph));  
81.    
82.        int determined=0;//没有决定  
83.        int c=0;  
84.        int t,k;  
85.        ArcNode *temp;  
86.    
87.        for(int i=0;i<m;++i){  
88.            scanf(" %s",relation);  
89.    
90.            if(alph[relation[0]-'A']==0){  
91.               alph[relation[0]-'A']=1; ++c;  
92.            }  
93.            if(alph[relation[2]-'A']==0){  
94.               alph[relation[2]-'A']=1;++c;  
95.            }  
96.    
97.            numbers[relation[2]-'A']++;//入度数加一  
98.            temp=new ArcNode;  
99.            temp->to=relation[2]-'A';  
100.            temp->next=NULL;  
101.    
102.            if(List[relation[0]-'A']==NULL){  
103.               List[relation[0]-'A']=temp;  
104.            }else{  
105.               temp->next=List[relation[0]-'A'];  
106.               List[relation[0]-'A']=temp;  
107.            }  
108.            if(determined==0){
     //如果顺序还没有决定下来  
109.               t=topSort(c);  
110. //            printf("t=%d,c=%d\n",t,c);  
111.               if(t==-1){  
112.                   determined=-1;k=i+1;  
113.               }else if(t==n){  
114.                   determined=1;k=i+1;  
115.               }  
116.            }  
117.        }  
118.    
119.        if(determined==-1){  
120.            printf("Inconsistency found after %d relations.\n",k);  
121.        }else if(determined==0){  
122.            printf("Sorted sequence cannot be determined.\n");  
123.        }else{  
124.            output[n]=0;  
125.            printf("Sorted sequence determined after %d relations: %s.\n",k,output);  
126.    
127.         }  
128.    
129.        //收回内存  
130.        for(int i=0;i<n;i++){  
131.            temp=List[i];  
132.            while(temp=NULL){  
133.               List[i]=temp->next;delete temp;temp=List[i];  
134.            }  
135.        }  
136.     }  
137.     return 0;  
138. }  
139.