这道题本质上是Floyd求传递闭包，所谓传递闭包，就是这个样子，非常的简单，即在一个传递闭包中元素之间都有某种关系。
这道题数据范围很小，因此我们可以开一个邻接矩阵，floyd[i][j]就表示i>j。当我们判断的时候很简单，当floyd[i][j]==floyd[j][i]==1时，就矛盾了，当floyd[i][j]==0且floyd[j][i]==0时，就说明i，j的大小关系不能确定。知道了这两个后，本题就不难了。首先去枚举前t个不等式组，每一次加一条边后求传递闭包。之后以此判断矛盾，排序成功，当t组枚举完之后，判断是否可以排序即可。
参考代码如下：
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
struct node
{
int nodee,num;
}f[10001];
int floyd[127][127],n,m,a1[100001],b1[100001],c1[100001];
char a,b,c;
bool cmp(node a,node b)
{
return a.num<b.num;
}
int main()
{
bool flag;
int pd=12345678;
while(1)
{
cin>>n>>m;
if(!n&&!m)return 0;
flag=0;
pd=0;
memset(floyd,0,sizeof(floyd));
for(int t=1;t<=m;t++)
{
cin>>a>>b>>c;
int x=a-‘A‘+1,y=c-‘A‘+1;
f[x].nodee=x;f[x].num=0;
f[y].num=0;f[y].nodee=y;
if(flag)continue;
if(b==‘<‘)floyd[x][y]=1;
else floyd[y][x]=1;
for(int k=1;k<=n;k++)
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
floyd[i][j]|=floyd[i][k]&floyd[k][j];
}
}
}
for(int i=1;i<=n;i++)
{
for(int j=i+1;j<=n;j++)
{
if(floyd[i][j]&&floyd[j][i])
{
flag=1;
cout<<"Inconsistency found after "<<t<<" relations."<<endl;
break;
}
}
if(flag)break;
}
if(flag)continue;
int fss=1;
for(int i=1;i<=n;i++)
{
if(pd!=0&&pd!=12345678)
{
fss=0;
break;
}
for(int j=i+1;j<=n;j++)
{
if(!floyd[i][j]&&!floyd[j][i])
{
fss=0;
if(t==m)
{
cout<<"Sorted sequence cannot be determined."<<endl;
flag=1;
break;
}
}
}
if(flag)break;
}
if(flag)continue;
if(fss==1)
{
pd=t;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(floyd[i][j]&&i!=j)f[j].num++;
}
}
sort(f+1,f+1+n,cmp);
cout<<"Sorted sequence determined after "<<pd<<" relations: ";
for(int i=1;i<=n;i++)cout<<char(f[i].nodee+‘A‘-1);
cout<<"."<<endl;
flag=1;
}
}
}
}
原文：https://www.cnblogs.com/szmssf/p/11027288.html