记录编号	577305	评测结果	AA
题目名称	Sorting It All Out	最终得分	100
用户昵称	lihaoze	是否通过	通过
代码语言	C++	运行时间	0.013 s
提交时间	2022-10-31 10:33:10	内存使用	2.87 MiB

#include "bits/stdc++.h"

using PII = std::pair<int, int>;

const int N = 30;
int n, m;
int dist[N][N], copy[N][N];

int floyd() {
    for (int k = 0; k < n; ++ k)
        for (int i = 0; i < n; ++ i)
            for (int j = 0; j < n; ++ j) {
                dist[i][j] |= dist[i][k] & dist[k][j];
                if (dist[i][j] && dist[j][i] && i != j) return -1;
            }
    for (int i = 0; i < n; ++ i)
        for (int j = 0; j < n; ++ j)
            if (!dist[i][j] && !dist[j][i] && i != j) return 0;
    return 1;
}

int main() {
    freopen("sortitallout.in", "r", stdin); 
    freopen("sortitallout.out", "w", stdout);
    while (std::cin >> n >> m, n && m) {
        memset(dist, 0, sizeof dist);
        bool flag = true;
        for (int i = 1; i <= m; ++ i) {
            char a, b, rel;
            std::cin >> a >> rel >> b, a -= 'A', b -= 'A';
            if (rel == '<') {
                dist[a][b] = 1;
            } else {
                dist[b][a] = 1;
            }
            if (flag) {
                memcpy(copy, dist, sizeof copy);
                int now = floyd();
                flag = !now;
                if (now == -1) {
                    std::cout << "Inconsistency found after " << i << " relations." << '\n';
                } else if (now == 1) {
                    std::cout << "Sorted sequence determined after " << i <<  " relations: ";
                    PII ans[N];
                    for (int j = 0; j < n; ++ j) {
                        ans[j] = std::make_pair(0, j + 'A');
                    }
                    for (int j = 0; j < n; ++ j) 
                        for (int k = 0; k < n; ++ k) 
                            if (dist[j][k]) {
                                ++ ans[j].first;
                            }
                    std::sort(ans, ans + n, std::greater<PII>());
                    for (int j = 0; j < n; ++ j) {
                        std::cout << char(ans[j].second);
                    }
                    std::cout << '.' << '\n';
                }
                memcpy(dist, copy, sizeof dist);
            }
        }
        if (flag) {
            std::cout << "Sorted sequence cannot be determined." << '\n';
        }
    }
    return 0;
}