原题地址：点击打开链接
该题用拓扑排序即可解决，建图之后先找入度为0的点，如果同时有2个或以上的顶点度数为0，则说明不可排序，如果拓扑排序结束后得到的答案小于顶点数则说明存在环，意思就是存在矛盾的关系式。
#include<stdio.h> #include<string.h> #include<queue> #include<vector> using namespace std; vector<int>next[26]; int p[26],pp[26],used[26],n; char result[30],str[6]; int TpSort() { queue<int>que; int res=0,u,v,i,size=0,book=0; for(i=0;i<n;i++) pp[i]=p[i]; for(i=0;i<n;i++) { if(pp[i]==0) { que.push(i); } } while(!que.empty()) { if(que.size()>1) //如果不止一个点的入度不为0则不可排序 book=1; u=que.front(); que.pop(); result[size++]=u+'A'; for(i=0;i<next[u].size();i++) //将该点所有的边删除，更新与其相连顶点的入度 { v=next[u][i]; pp[v]--; if(pp[v]==0) que.push(v); } } result[size]='\0'; if(size<n) return -1; if(book==1) return 0; else return 1; } int main() { int m,i,j,u,v,state,mark; while(scanf("%d%d",&n,&m)&&(n||m)) { state=0; getchar(); for(i=0;i<n;i++) { p[i]=0; next[i].clear(); } for(i=0;i<m;i++) { gets(str); if(state==1||state==-1) //如果已经可排序或者循环，则不用再继续判断，但仍然要继续输入 continue; u=str[0]-'A'; v=str[2]-'A'; for(j=0;j<next[u].size();j++) { if(v==next[u][j]) break; } if(j==next[u].size()) { next[u].push_back(v); p[v]++; //记录定点的入度 memset(used,0,sizeof(used)); state=TpSort(); if(state==1||state==-1) { mark=i+1; } } } if(state==-1) { printf("Inconsistency found after %d relations.\n",mark); } else if(state==0) { printf("Sorted sequence cannot be determined.\n"); } else { printf("Sorted sequence determined after %d relations: %s.\n",mark,result); } } return 0; }