View Code of Problem 223

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cctype>
#include<map>
#include<stack>
#define INF 0x3f3f3f3f
using namespace std;
const int maxn = 27;
int rd[maxn];
int edge[maxn][maxn];
//bool vis[maxn];
int s[maxn];

//拓扑排序 模板 
int tpSort(int n)
{
	bool flag;
	int i,j,rd1[27],temp;
	stack<int> s1;
	memcpy(rd1,rd,sizeof(rd1));
	for(i=1;i<=n;i++)
		if(rd1[i]==0)
			s1.push(i);
	i=0;
	flag=0;
	while(s1.size()!=0)
	{
		if(s1.size()>1)
			flag=1;
		temp=s1.top();
		s1.pop();
		s[++i]=temp;
		for(j=1;j<=n;j++)
			if(edge[temp][j]==1&&--rd1[j]==0)
				s1.push(j);
	}
	if(i<n)
		return 1;//有环，无法形成n个元素的拓扑排序 
	else if(flag==1) 
		return 2;//没有环，但入度为0的点不唯一，当前没有形成拓扑排序，但可以形成n个元素的拓扑排序 
	return 3;//已经形成n个元素的拓扑排序 
}

int main(){
	int n,m;
	ios::sync_with_stdio(false);
    while(~scanf("%d %d",&n,&m)){
        if(!n||!m)
			break;
		bool flag=true;
        memset(rd, 0, sizeof(rd));
        memset(edge, 0, sizeof(edge));
        char ss[6];
		for(int i=1;i<=m;i++){
			scanf("%s",ss);
			if(flag){
				if(edge[ss[0]-'A'+1][ss[2]-'A'+1]==0){
					edge[ss[0]-'A'+1][ss[2]-'A'+1]=1;
					rd[ss[2]-'A'+1]++;
				}
				
				int t=tpSort(n);
				if(t==1)
		        	flag=false,cout<<"Inconsistency found after "<<i<<" relations."<<endl;	
		        else if(t==3){
		        	flag=false;
					cout<<"Sorted sequence determined after "<<i<<" relations: ";
					for(int j=1;j<=n;j++)
						cout<<(char)(s[j]+'A'-1);
					cout<<"."<<endl;
				}
			}
			
	        	
		}
		if(flag)
			cout<<"Sorted sequence cannot be determined."<<endl;
    }
    
    
    return 0;
}