排序

题目

题目描述

一个不同的值的升序排序数列指的是一个从左到右元素依次增大的序列，例如，一个有序的数列A,B,C,D 表示A<B,B<C,C<D。在这道题中，我们将给你一系列形如A<B的关系，并要求你判断是否能够根据这些关系确定这个数列的顺序。

输入格式

第一行有两个整数n,m，n表示需要排序的元素数量，2<=n<=26，第1到n个元素将用大写的A,B,C,D…表示。m表示将给出的形如A<B的关系的数量。

接下来有m行，每行有3个字符，分别为一个大写字母，一个<符号，一个大写字母，表示两个元素之间的关系。

输出格式

若根据前x个关系即可确定这n个元素的顺序yyy…y（如ABC），输出

Sorted sequence determined after xxx relations: yyy…y.

若根据前x个关系即发现存在矛盾（如A<B,B<C,C<A），输出

Inconsistency found after 2 relations.

若根据这m个关系无法确定这n个元素的顺序，输出

Sorted sequence cannot be determined.

（提示：确定n个元素的顺序后即可结束程序，可以不用考虑确定顺序之后出现矛盾的情况）

输入输出样例

输入#1

4 6
A<B
A<C
B<C
C<D
B<D
A<B

输出#1

Sorted sequence determined after 4 relations: ABCD.

输入#2

3 2
A<B
B<A

输出#2

Inconsistency found after 2 relations.

输入#3

26 1
A<Z

输出#3

Sorted sequence cannot be determined.

解题思路

第一种情况：

我们记录一条最长链的长度，如果 l e n = = n len==n len==n就输出队列里的内容

第二种情况

如果输入时 x = = y x==y x==y或者 d u [ i ] ! = 0 du[i]!=0 du[i]!=0则说明它有环，则是第二种情况

第三种情况

如果前两种情况都不是，就是第三种情况

code（注：一边输入一边拓扑，以保证第二种情况）

#include<iostream>
#include<cstdio>
using namespace std;

int n,m,b[1000],v[1000],d[1000];
int head[1000],tot,f[1000],l,ans[1000];

struct abc{
	int to,next;
}s[1000];

void add(int x,int y)
{
	s[++tot]=(abc){y,head[x]};
	head[x]=tot; 
}

void tp()
{
	int hd=0,tl=0;
	l=0;
	for(int i=1;i<=n;i++)
	{
		ans[i]=f[i]=v[i]=0;
		d[i]=b[i];
		if(d[i]==0)
		{
			tl++;
			v[i]=1;
			f[tl]=i;
			ans[i]=1;
		}
	}
	while(hd<tl)
	{
		hd++;
		int x=f[hd];
		for(int i=head[x];i;i=s[i].next)
		{
			int y=s[i].to;
			if(v[y]) continue;
			d[y]--;
			ans[y]=max(ans[x]+1,ans[y]);
			l=max(l,ans[y]);
			if(d[y]==0)
			{
				v[y]=1;
				f[++tl]=y;
			}
		}
	}
}

int main()
{
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		char a;
		int x,y;
		cin>>a;
		x=a-64;
		cin>>a>>a;
		y=a-64;
		if(x==y)
		{
			printf("Inconsistency found after %d relations.",i);
			return 0;
		}
		add(x,y);
		b[y]++;
		tp();
		for(int j=1;j<=n;j++)
			if(d[j]>0)
			{
				printf("Inconsistency found after %d relations.",i);
				return 0;
			} 
		if(l==n)
		{
			printf("Sorted sequence determined after %d relations: ",i);
			for(int j=1;j<=n;j++)
				printf("%c",f[j]+64);
			printf(".");
			return 0;
		}
	}
	printf("Sorted sequence cannot be determined.");
	return 0;
}