记录编号	568437	评测结果	AAWAAAAAAA
题目名称	ABC排序	最终得分	90
用户昵称	遥时_彼方	是否通过	未通过
代码语言	C++	运行时间	0.000 s
提交时间	2022-01-02 20:27:50	内存使用	0.00 MiB

#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
using namespace std;
const int N=30;
int nc;
int mc;
int ch[N][N];
int fa[N][N];
int ps[N];
int pss[N];
void clear(queue<int> &x)
{
	queue<int> y;
	swap(x,y);
}
queue<int> pl;
void pd(int cl,int x,int y)
{
//	cout<<"PA3\n";
	memset(ps,0,sizeof(ps));
	memset(pss,0,sizeof(pss));
	clear(pl);
	pl.push(y);
	ps[y]=1;
	while(pl.size())
	{
		for(int r=pl.front(),i=1;i<=nc;i++)
		{
			if(ch[y][i]&&!ps[i])
			{
				ps[i]=1;
				pl.push(i);
			}
		}
		pl.pop();
	}
	pl.push(x);
	pss[x]=1;
	while(pl.size())
	{
		for(int r=pl.front(),i=1;i<=nc;i++)
		{
			if(fa[x][i]&&!pss[i])
			{
				pss[i]=1;
				pl.push(i);
			}
		}
		pl.pop();
	}
	for(int i=1;i<=nc;i++) 
	if(ps[i]&&pss[i])
	{
		cout<<"Inconsistency found after "<<cl<<" relations.\n";
		exit(0);
	}
	return;
}
void add(int cl,int x,int y)
{
	memset(ps,0,sizeof(ps));
	memset(pss,0,sizeof(pss));
	clear(pl);
	pl.push(y);
	while(pl.size())
	{
		for(int r=pl.front(),i=1;i<=nc;i++)
		{
//			cout<<"PA5\n";
			if(ch[y][i]&&!ps[i])
			{
				ps[i]=1;
				pl.push(i);
			}
		}
		pl.pop();
	}//在y中找(所有)儿子 
	for(int i=1;i<=nc;i++)
	{
		if(ch[x][i]&&ps[i])
		{
			fa[i][x]=0;
			ch[x][i]=0;
		}
	}
	memset(ps,0,sizeof(ps));
	memset(pss,0,sizeof(pss));
	clear(pl);
	pl.push(y);
	while(pl.size())
	{
		for(int r=pl.front(),i=1;i<=nc;i++)
		{
//			cout<<"PA5\n";
			if(fa[y][i]&&!ps[i])
			{
				ps[i]=1;
				pl.push(i);
			}
		}
		pl.pop();
	}//在y中找(所有)父亲 
	for(int i=1;i<=nc;i++)
	{
		if(fa[x][i]&&ps[i])
		{
			fa[y][i]=0;
			ch[i][y]=0;
		}
	}
	fa[y][x]=1;
	ch[x][y]=1;
//	cout<<"XY:"<<x<<" "<<y<<endl;
}
int ans[N];
int aj;
void re(int cl)
{
	memset(ans,0,sizeof(ans));
	aj=0;
	int rs=1;
	int s1;
	int rp=1;
	while(rp)
	{
//		cout<<"PA6\n";
		rp=0;
		for(int i=1;i<=nc;i++) rp+=ch[rs][i];
		if(rp>1) return;
		rp=0;
		for(int i=1;i<=nc;i++)
		{
//			if(i==rs) continue;
			rp+=fa[rs][i];
			if(fa[rs][i]) s1=i;
		}
//		cout<<rs<<" "<<rp<<" "<<s1<<"\n";
		if(rp>1) return;
		if(rp!=0) rs=s1;
	}
	rp=1;
	while(rp)
	{
//		cout<<"PA7\n";
	    ans[++aj]=rs;
		rp=0;
		for(int i=1;i<=nc;i++) rp+=fa[rs][i];
		if(rp>1) return;
		rp=0;
		for(int i=1;i<=nc;i++)
		{
			if(i==rs) continue;
			rp+=ch[rs][i];
			if(ch[rs][i]) s1=i;
		}
//		cout<<"RE:"<<rs<<" "<<rp<<endl;
		if(rp>1) return;
		if(rp!=0) rs=s1;
	}
	if(aj!=nc) return;
	cout<<"Sorted sequence determined after ";
	cout<<cl<<" relations: ";
	for(int i=1;i<=aj;i++) cout<<(char)('@'+ans[i]);
	cout<<".\n";
	exit(0);
}
int main()
{
	freopen("abcsort.in","r",stdin);
	freopen("abcsort.out","w",stdout);
    cin>>nc;
    cin>>mc;
    char s1,s2;
    int s3,s4;
    for(int i=1;i<=mc;i++)
    {
    	cin>>s1;
    	cin>>s2;
    	cin>>s2;
    	s1-='@';
    	s2-='@';
    	s3=s1;
    	s4=s2;
//    	cout<<s3<<" "<<s4<<endl;
//    	cout<<"PA1\n";
    	pd(i,s3,s4);//first:判断矛盾
//		cout<<"PA2\n"; 
    	add(i,s3,s4);//second:连接
    	re(i);//third:是否确认 
	}
    cout<<"Sorted sequence cannot be determined.\n";
	return 0;
}