在老师的建议下，本人决定从现在开始每做一道题都写解题报告，嘿嘿，以前从没写过。下面步入正题：
题目的本质就是要对输入数据进行拓扑排序，需要注意的有一下几点：
（1）m组关系，每输入一组都要重新进行一趟拓扑排序
（2）只要找出确定顺序，只需要把剩余数据读完即可，不用再排序，否则可能WA，本人认为这是这道题目的一个bug
（3）存在不确定的顺序时，仍然需要判断是否存在环，如果存在环，则输出矛盾。
下面给出源代码：
#include <iostream>
#include <string>
#include <memory.h>
using namespace std;
bool finish,map[27][27],cir[27][27];
string s;
int f,e,i,j,n,m,d[27],pre[27];
bool c()
{
int i,j,k;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
cir[i][j]=map[i][j];
for(k=1;k<=n;k++)
for(i=1;i<=n;i++)
if(i!=k)
for(j=1;j<=n;j++)
if(j!=k&&cir[i][k]&&cir[k][j])
cir[i][j]=true;
for(i=1;i<=n;i++)
if(cir[i][i])
return true;
return false;
}
bool deal(int x)
{
int i,j,s,t,flag=0;
memset(pre,0,sizeof(pre));
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(i!=j&&map[j][i])
pre[i]++;
memset(d,0,sizeof(d));
s=t=0;
while(flag==0)
{
flag=1;
for(i=1;i<=n;i++)
if(pre[i]==0)
{
t++;
d[t]=i;
pre[i]--;
flag=0;
}
if(t-s>1)
return false;
for(i=s+1;i<=t;i++)
for(j=1;j<=n;j++)
if(d[i]!=j&&map[d[i]][j])
pre[j]--;
s=t;
}
if(t<n)
return false;
return true;
}
int main()
{
freopen("data.in","r",stdin);
freopen("data.out","w",stdout);
while(cin>>n>>m)
{
if(n==0&&m==0)
break;
memset(map,false,sizeof(map));
finish=false;
for(i=1;i<=m;i++)
{
cin>>s;
if(finish)
continue;
f=s[0]-64;
e=s[2]-64;
map[f][e]=true;
if(c())
{
cout<<"Inconsistency found after "<<i<<" relations."<<endl;
finish=true;
}
if(finish)
continue;
if(deal(i))
{
cout<<"Sorted sequence determined after "<<i<<" relations: ";
for(j=1;j<=n;j++)
cout<<(char)(d[j]+64);
cout<<"."<<endl;
finish=true;
}
}
if(!finish)
cout<<"Sorted sequence cannot be determined."<<endl;
}
fclose(stdin);
fclose(stdout);
return 0;
}
找环的过程我用得图的传递闭包，自己感觉这是个笨方法，因为这种算法找出了所有的环，但我们只需要知道是否存在环。如果哪位朋友有更好的方法，欢迎建议和指正。