cpp
#include<bits/stdc++.h>
using namespace std;
int n,m,c[610];
bool flag;
int tmp;
struct ty{
int t;//t存放这条边和哪条边连接
int next; //next存放下一个点的下标是谁
}edge[100010];
int head[1010];//记录下一个节点指向的下标
int cnt=0;
void addedge(int x,int y)//链式前向星 存储图
{
edge[++cnt].t = y;
edge[cnt].next = head[x];
head[x] = cnt;
}
int inc[1010]; //存放这条边有几个元素入度
queue<int> q;
int tuopu()//拓扑排序
{
bool flag2=0;
if(flag==0)
{
for(int i=1;i<=n;i++)//访问所有的点
{
if(inc[i] == 0)//是一个可以直接拿出来的点
{
flag2=1;
q.push(i);
}
}
}
else if(flag==1)
{
for(int i=1;i<=tmp;i++)//访问所有的点
{
if(inc[i] == 0)//是一个可以直接拿出来的点
{
flag2=1;
q.push(i);
}
}
}
if(flag2==0) return 0;//讨论矛盾的情况
int tot=0;//记录已经输出的点的个数
while(!q.empty())
{
int x=q.front();
cout<<x<<' '<<endl;
q.pop();
tot++;
for(int i=head[x]; i!=-1; i=edge[i].next)//访问与x相邻的所有的边
{
inc[edge[i].t]--;
if(inc[edge[i].t] == 0)
q.push(edge[i].t);
}
}
cout<<"tot="<<tot<<endl;
if(flag==1)//所给的条件满足关系
{
if(tot != tmp) return 0;
else return 1;//能成功找到
}
else
{
if(tot != n) return 0;
else return 1;//能成功找到
}
}
int main()
{
cin>>n>>m;
string s="";
memset(head,-1,sizeof(head));
for(int i=1;i<=m;i++)
{
flag=0;
char x,y;
char t;
cin>>x>>t>>y;
int a=x-'0'; int b=y-'0';
// c[a]=1; c[b]=1;
if(c[a]==0) s+=x;
if(c[b]==0) s+=y;
c[a]=1; c[b]=1;
if(t=='>')
{
addedge(a,b);
inc[b]++;
}
else
{
addedge(b,a);
inc[a]++;
}
tmp=s.size();
// cout<<"tmp="<<tmp<<" ";
if(tmp<n) flag=1;
// cout<<i<<" "<<flag<<endl;
if(flag==0 && tuopu()==1)//能成功找到
{
sort(s.begin(),s.end());
cout<<"Sorted sequence determined after "<<i<<" relations: "<<s<<"."<<endl;
return 0;
}
else if(tuopu()==0 && i!=m )//&& flag)//第二种情况
{
cout<<"Inconsistency found after "<<i<<" relations." <<endl;
// return 0;
}
else if(tuopu()==0 && i==m)
{
cout<<"Sorted sequence cannot be determined."<<endl;
return 0;
}
}
return 0;
}