P1347 排序

#include <bits/stdc++.h>
#define N 20000
#define M 5001
#define INF 0x3f3f3f3f3f
#define ll long long
using namespace std;
ll cd[N],rd[N],to,res,ct;
vector<int> a[N];
ll f[N],top,so[N],x,fa[N];
char s[3];
ll o,p;
ll n,m;
bool v[N];
int topo() {
	top=0;
	ct=0;
	bool fin=false;
	bool vis=false;
	for(int i=1; i<=26; i++) {
		if(rd[i]==0&&v[i]) {
			if(!vis)	vis=true;
			else		fin=true;
			f[++top]=i;
			so[++ct]=i;
		}
	}
	if(top==0) {
		return 1;
	}
	while(top>0) {
		vis=false;
		x=f[top--];
		ct++;
		so[ct]=x;
		for(int i=0; i<a[x].size(); i++) {
			to=a[x][i];
			if(--rd[to]==0) {
				f[++top]=to;
				if(!vis)	vis=true;
				else	fin=true;
			}
		}
	}
	if(ct!=res)	return 1;
	if(fin)		return 2;
	return 0;
}
int main() {
	cin>>n>>m;
	for(int i=1; i<=m; i++) {
		for(int j=0; j<3; j++) {
			cin>>s[j];
		}
		o=s[0]-'A'+1;
		p=s[2]-'A'+1;
		a[o].push_back(p);
		rd[p]++;
		cd[o]++;
		if(!v[o]) {
			v[o]=true;
			res++;
		}
		if(!v[p]) {
			v[p]=true;
			res++;
		}
		if(topo()==1) {
			cout<<"Inconsistency found after "<<m<< " relations.";
			return 0;
		}
		if(ct==n&&!topo()) {
			cout<<"Sorted sequence determined after "<<n<<" relations: ";
			for(int j=0; j<=n-1; j++) {
				cout<<char(so[j]+'A'-1);
			}
			cout<<".";
			return 0;
		}
	}
	cout<<"Sorted sequence cannot be determined.";
}