进我的博客浏览：https://www.cnblogs.com/lzxzy-blog/p/10328346.html









#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int MAXN=2500;
int n,m,cas,id;

struct edge
{
	int v,nx;
}set[MAXN];
int head[30],d[30],ok[30],write[30];
queue<int> Q;

void Addedge(int u,int v)
{
	id++;set[id].v=v;set[id].nx=head[u];
	head[u]=id;
}

int bfs()
{
	cas=0;
	while(!Q.empty())Q.pop();
	int out=1,t,u;t=0;
	for(int i=1;i<=n;i++)
		if(!ok[i])
		{
			t++;Q.push(i);
		}
	if(t>1)out=0;
	while(!Q.empty())
	{
		u=Q.front();Q.pop();t=0;write[++cas]=u;
		for(int k=head[u];k>0;k=set[k].nx)
		{
			ok[set[k].v]--;
			if(!ok[set[k].v])
			{
				t++;Q.push(set[k].v);
			}
		}
		if(t>1)out=0;
	}
	for(int i=1;i<=n;i++)if(ok[i]>0){out=-1;break;}
	return out;
}

char print()
{
	for(int i=1;i<=cas;i++)printf("%c",(char)(write[i]+64));
	return '.';	
}

int main()
{
	while(~scanf("%d%d",&n,&m))
	{
		memset(write,0,sizeof(write));	
		memset(d,0,sizeof(d));	
		memset(head,-1,sizeof(head));
		id=0;
		int now=0,loca;
		char a,b,c;
		if(n==0 && m==0)break;
		for(int i=1;i<=m;i++)
		{
			cin>>a>>b>>c;
			if(b=='<')
			{
				Addedge(a-64,c-64);d[c-64]++;
			}
			else 
			{
				Addedge(c-64,a-64);d[a-64]++;
			}
			if(now==0)
			{
				for(int j=1;j<=n;j++)ok[j]=d[j];
				now=bfs();loca=i;
			}
		}
		if(now==0)puts("Sorted sequence cannot be determined.");
		else if(now==1)printf("Sorted sequence determined after %d relations: ",loca),printf("%c\n",print());
		else printf("Inconsistency found after %d relations.\n",loca);
	}
	return 0;
}