一道拓扑的经典题，但理解题目让我很伤。
大意是说给出关于n个字母的偏序关系，让你判断是否有唯一序列或有环（输出当前是第几步，如果有唯一序列还有输出），如果都读完了还不能确定，就输出另一种情况。
按照题意，每读入一步就走一遍topo来判断。
有一个坑点：就算中间找到并退出了还是要把剩下的读完。
具体看CODE
#include<iostream> #include<cstring> using namespace std; struct edge { int to,next; }e[1005]; int n,m,ru[30],temp[30],head[1005],i,j,k,flag; bool sign; char a,b,ans[30]; inline void add(int x,int y) { e[++k].to=y; e[k].next=head[x]; head[x]=k; } inline int topo() { int flag=2; for (int i=1;i<=n;++i) { int res=0,tot=0; for (int j=1;j<=n;++j) if (!ru[j]) ++tot,res=j; if (tot>=2) flag=3; if (tot==0) return 1; ru[res]--; ans[i-1]=res+'A'-1; for (int j=head[res];j!=-1;j=e[j].next) ru[e[j].to]--; } return flag; } int main() { //freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout); for (;;) { cin>>n>>m; if (n==0&&m==0) break; memset(temp,0,sizeof(temp)); memset(head,-1,sizeof(ru)); memset(e,-1,sizeof(e)); memset(ans,0,sizeof(ans)); sign=1; k=0; for (i=1;i<=m;++i) { cin>>a; getchar(); cin>>b; if (!sign) continue; for (j=0;j<30;++j) ru[j]=temp[j]; add(a-'A'+1,b-'A'+1); ru[b-'A'+1]++; temp[b-'A'+1]++; flag=topo(); if (flag==1) printf("Inconsistency found after %d relations. ",i),sign=0; if (flag==2) printf("Sorted sequence determined after %d relations: %s. ",i,ans),sign=0; } if (sign) puts("Sorted sequence cannot be determined."); } return 0; }