源码

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
using namespace std;
const int N = 40,M = 610;
int h[N],e[M],ne[M],idx,din[N],temp_din[N];
int mode = 0;
int n,m;
string ans = "";

void add(int a,int b)
{
	ne[idx] = h[a],e[idx] = b,h[a] = idx ++;
	din[b] ++;
}

void topsort()
{
	ans = "";
	mode = 0;
	bool key;
	queue<int> q;
	for(int i = 1; i <= n; i ++)
		temp_din[i] = din[i];
	for(int i = 1; i <= n; i ++)
		if(!temp_din[i])
			q.push(i);
	if(q.size() > 1)
		key = true;
	while(q.size())
	{
		int k = q.front();
		ans += char(k+'A'-1);
		q.pop();
		for(int i = h[k];~i;i = ne[i])
		{
			int j = e[i];
			temp_din[j] --;
			if(!temp_din[j])
				q.push(j);
		}
		if(q.size()>1)
			key = true;		 
	}
	if(ans.size() < n)
		mode = 1;
	if(ans.size() == n&&!key)
		mode = 2;
}

int main()
{
	cin>>n>>m;
	memset(h,-1,sizeof(h));
	string temp;
	for(int i = 1; i <= m; i ++)
	{
		cin>>temp;
		add(temp[0] - 'A'+1,temp[2] - 'A'+1);
		topsort();
//		cout<<ans<<endl;
		if(mode == 1)
		{
			cout<<"Inconsistency found after "<<i<<" relations.\n";
			return 0;
		}
		if(mode == 2)
		{
			cout<<"Sorted sequence determined after "<<i<<" relations: "<<ans<<".\n";
			return 0;
		}
	}
	cout<<"Sorted sequence cannot be determined.\n";
    return 0;
}

测试点

26 25
A<C
C<E
E<G
G<I
I<K
K<M
M<O
O<Q
Q<S
S<U
U<W
W<Y
Y<Z
Z<B
B<D
D<F
F<H
H<J
J<L
L<N
N<P
P<R
R<T
T<V
V<X

幸好可以看数据，不然得修半天