记录编号	559234	评测结果	AA
题目名称	Sorting It All Out	最终得分	100
用户昵称	yrtiop	是否通过	通过
代码语言	C++	运行时间	0.000 s
提交时间	2021-02-21 19:32:51	内存使用	0.00 MiB

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 30;
const int INF = 0x3f3f3f3f;
int f[maxn][maxn];
int in[maxn],out[maxn];
char s[3],ans[maxn];
int sum(char c) {
	return c - 'A' + 1;
}
int n,m;
int main() {
	freopen("sortitallout.in","r",stdin);
	freopen("sortitallout.out","w",stdout);
	bool flag,cur = true;
	while(~ scanf("%d%d",&n,&m)) { 
		if(!n&&!m)break ;
		memset(f , 0 , sizeof(f));
		memset(in , 0 , sizeof(in));
		memset(out , 0 , sizeof(out));
		memset(ans , 0 , sizeof(ans));
		int x,y;
		flag = false;
		int t = 0;
		cur = true;
		for(int i = 1;i <= m;++ i) {
			scanf("%s",s);
			x = sum(s[0]);
			y = sum(s[2]);
			if(flag)continue ;
			if(!cur)continue ;
			if((f[x][y] == INF||f[y][x] == 1)&&(cur == true)) {
				printf("Inconsistency found after %d relations.\n",i);
				cur = false;
			}
			if(!cur)continue ;
			if(!f[x][y]) {
				f[x][y] = 1;
				++ out[x];
			}
			if(!f[y][x]) {
				f[y][x] = INF;
				++ in[y];
			}
//			f[x][y] = 1;
//			++ out[x];
//			++ in[y];
//			f[y][x] = INF;
			for(int j = 1;j <= n;++ j) {
				if(f[x][j] == INF) {
					if(f[j][x] == INF||f[j][y] == INF||f[y][j] == 1) {
						printf("Inconsistency found after %d relations.\n",i);
						cur = false;
						break ;
					}
					if(!f[j][y]) {
						f[j][y] = 1;
						++ out[j];
					}
					if(!f[y][j]) {
						f[y][j] = INF;
						++ in[y];
					}
//					f[j][y] = 1;
//					f[y][j] = INF;
//					++ out[j];
//					++ in[y];
				}
				if(f[y][j] == 1) {
					if(f[j][y] == 1||f[j][x] == 1||f[x][j] == INF) {
						printf("Inconsistency found after %d relations.\n",i);
						cur = false;
						break ;
					}
					if(!f[x][j]) {
						f[x][j] = 1;
						++ out[x];
					}
					if(!f[j][x]) {
						f[j][x] = INF;
						++ in[j];
					}
//					f[x][j] = 1;
//					f[j][x] = INF;
//					++ in[j];
//					++ out[x];
				}
			}
			if(!cur)continue ;
			int cnt = 0; 
			for(int j = 1;j <= n;++ j) {
				if(in[j] + out[j] == n - 1) {
					++ cnt;
				}
			}
			if(flag)continue ;
			if(cnt == n&&flag == false) {
				t = i;
				flag = true;
				for(int i = 1;i <= n;++ i) {
					ans[in[i]] = (char)(i - 1 + 'A');
				}
			}
		}
		if(!cur)continue ;
		if(!flag) {
			puts("Sorted sequence cannot be determined.");
		}
		else {
			printf("Sorted sequence determined after %d relations: ",t);
			for(int i = 0;i < n;++ i) {
				for(int j = 1;j <= n;++ j) {
					if(in[j] == i) {
						printf("%c",j - 1 + 'A');
						break ;
					}
				}
			} 
			printf(".\n");
		}
	}
	fclose(stdin);
	fclose(stdout);
	return 0;
}