记录编号	581214	评测结果	AA
题目名称	Sorting It All Out	最终得分	100
用户昵称	┭┮﹏┭┮	是否通过	通过
代码语言	C++	运行时间	0.009 s
提交时间	2023-07-31 15:37:45	内存使用	2.87 MiB

#include <bits/stdc++.h>
using namespace std;
const int N = 30;
int n,m;
int a[N][N],d[N][N];
pair<int,char>ans[N];
int floyd(){
    for(int k = 1;k <= n;k++)
        for(int i = 1;i <= n;i++)
            for(int j = 1;j <= n;j++){
                d[i][j] |= (d[i][k] & d[k][j]);
                if(d[i][j] && d[j][i] && i != j)return -1;//有矛盾 
            }
    for(int i = 1;i <= n;i++)
        for(int j = 1;j <= n;j++)
            if(!d[i][j] && !d[j][i] && i != j)return 0;//未包含全部 
    return 1;//符合 
}
int main(){
    freopen("sortitallout.in","r",stdin);
    freopen("sortitallout.out","w",stdout);
    //floyd求传递闭包 
    while(cin>>n>>m && n){//多组数据 
        bool flag = 1;
        memset(ans,0,sizeof(ans));//要！！！重！！！置！！！ 
        memset(a,0,sizeof(a));
        memset(d,0,sizeof(d));
        for(int i = 1;i <= m;i++){
            char c1,c2,c3;
            cin>>c1>>c2>>c3;
            d[c1-'A'+1][c3-'A'+1] = 1;//d数组 
            int x = floyd();
            if(flag){
                if(x == -1)
                    printf("Inconsistency found after %d relations.\n",i),flag = 0;//矛盾 
                else if(x == 1){
                    for(int j = 1;j <= n;j++)ans[j].second = char(j + 'A' - 1);
                    for(int j = 1;j <= n;j++)
                        for(int k = 1;k <= n;k++)
                            if(d[j][k] == 1)ans[j].first++;//统计大于j的全部 
                    sort(ans+1,ans+1+n);//排序 
                    printf("Sorted sequence determined after %d relations:",i);
                    for(int j = n;j >= 1;j--){//最小的有更多个大于的，即ans[j].first更大 
                        cout<<ans[j].second;//由小到大输出 
                    }
                    printf(".\n");
                    flag = 0;
                }
            }
        }
        if(flag)
            printf("Sorted sequence cannot be determined.\n");//未包含全部 
    }
    
    
    return 0;
    
}