算法标签：

拓扑排序

题解：

这道题的核心在于依据给定的一组形如 “A < B” 的关系，来判定是能够确定一个升序的排序序列，还是存在关系不一致的情况，亦或是无法确定排序序列。代码采用拓扑排序算法解决此问题，具体思路为：首先进行输入处理，读取要排序的对象数量 n 以及关系数量 m，随后在循环中读取 m 个关系，将这些关系存储于邻接矩阵 mp 中，并同步更新每个节点的入度 in。接着进行拓扑排序，每次读取一个关系后，调用 Topo 函数。在 Topo 函数内，先把原始入度复制到 inn 数组，防止对原始入度造成修改，然后进行 n 次循环，每次都去寻找一个入度为 0 的节点。若在某次循环中未找到入度为 0 的节点，那就表明存在环，此时返回 - 1；若在某次循环中找到多个入度为 0 的节点，意味着排序不唯一，将 f 标记为 0；而每次找到一个入度为 0 的节点后，需将其入度减 1，同时把与该节点相邻的节点的入度也减 1。最后进行结果判断，若 Topo 函数返回 0，说明无法确定排序序列；若返回 - 1，说明存在环，即关系不一致；若返回 1，说明已经确定排序序列，此时再次调用 Topo 函数输出排序结果。

#include <iostream>
#include <cstring>
using namespace std;

const int MAXN = 26;
int in[MAXN], inn[MAXN], n;
int mp[MAXN][MAXN];

// 拓扑排序函数，op 为 1 时输出排序结果，为 0 时不输出
int Topo(int op) {
    int i, j, k, f = 1;
    // 将原始入度复制到 inn 数组，避免修改原始入度
    for (i = 0; i < n; ++i)
        inn[i] = in[i];
    // 进行 n 次循环，每次找出一个入度为 0 的节点
    for (i = 0; i < n; ++i) {
        k = -1;
        // 遍历所有节点，找出入度为 0 的节点
        for (j = 0; j < n; ++j) {
            if (!inn[j]) {
                // 如果已经找到过入度为 0 的节点，说明排序不唯一
                if (k != -1) f = 0;
                k = j;
            }
        }
        j = k;
        // 如果没有找到入度为 0 的节点，说明存在环，返回 -1
        if (j == -1) return -1;
        // 如果 op 为 1，输出当前节点对应的字母
        if (op) cout << char('A' + j);
        // 将当前节点的入度减 1，标记为已处理
        inn[j]--;
        // 遍历所有节点，将与当前节点相邻的节点的入度减 1
        for (k = 0; k < n; ++k)
            inn[k] -= mp[j][k];
    }
    // 如果 op 为 1，输出换行符
    if (op)
        cout << "." << endl;
    // 返回排序结果，1 表示排序唯一，0 表示排序不唯一
    return f;
}

int main() {
    int f, m, i, a, b, x;
    string st;
    while (cin >> n >> m && n && m) {
        // 初始化邻接矩阵和入度数组
        memset(mp, 0, sizeof(mp));
        memset(in, 0, sizeof(in));
        // f 用于标记是否已经确定排序结果，x 用于记录处理的关系数量
        f = 0;
        x = -1;
        // 循环读取 m 个关系
        for (i = 1; i <= m; ++i) {
            cin >> st;
            // 获取关系中的两个节点
            a = st[0] - 'A';
            b = st[2] - 'A';
            // 如果是大于关系，交换 a 和 b
            if (st[1] == '>') {
                a += b;
                b = a - b;
                a -= b;
            }
            // 如果已经确定排序结果，跳过后续关系
            if (f) continue;
            // 更新邻接矩阵和入度
            mp[a][b]++;
            in[b]++;
            // 调用拓扑排序函数进行判断
            f = Topo(0);
            // 记录当前处理的关系数量
            x = i;
        }
        // 如果 f 为 0，说明无法确定排序序列
        if (!f) cout << "Sorted sequence cannot be determined." << endl;
        // 如果 f 为 -1，说明存在环，关系不一致
        else if (f == -1) cout << "Inconsistency found after " << x << " relations." << endl;
        // 否则，说明已经确定排序序列
        else {
            cout << "Sorted sequence determined after " << x << " relations: ";
            // 再次调用拓扑排序函数输出排序结果
            Topo(1);
        }
    }
    return 0;
}