原题：https://fjnuacm.top/d/junior/p/542?tid=6363ac4a691055e12dd289de

最短路题单，但是可以用拓扑（

题意

给定 \(A - Z\) 中前 \(n\) 个字母的大小顺序，且都为小于关系，共有 \(m\) 个条件，从前往后判断满足所有条件的序列是否存在且唯一。

对于从前往后的 \(t\) 次遍历中，若能确定最后输出，则略过后面的输入。

1. 有唯一解，输出 \(Sorted \ sequence \ determined \ after \ t \ relations: yyy...y.\)

2. 有多解（冲突），输出 \(Inconsistency \ found \ after \ t \ relations.\)

3. 无解（没有给全所有点的条件），输出 \(Sorted \ sequence \ cannot \ be \ determined.\)

思路

因为题面提到需要整个序列的顺序输出，而联想到拓扑排序，它可以将一个有向图转换成一个有先后顺序的序列，这正是我们需要的。

一切都一样，只是我们的有向图多了一个条件：

除了根和叶外，其他节点都是入度和出度为 \(1\) 的。

联想到拓扑排序的实现，若我们在每次循环的时候都判断一下队列的元素个数，大于 \(1\) 标记有多解，即可满足上述条件了。

当然，为了计算 \(t\)，跑一遍拓扑是不够的，我们要在加边的同时拓扑，来判断在加入这个条件后是否出现了多解或者无解。

考虑到入度的计算，不采用先加完边再跑拓扑的做法。

翻车实录

1. 注意输出的优先级，如果冲突且无解，应该输出冲突。

2. \(POJ\) 远端题，不要用万能头和 \(for-each\) 语句。

对应AC代码

#include <cstdio>
#include <vector>
#include <queue>
#include <cstring>

using namespace std;

int n, m, inDegree[30], copyInDegree[30], visited[30][30];
vector<int> edges[30], ans;

bool addEdge(int x, int y) { //在邻接表中添加一条有向边
    if(visited[x][y]) return true;
    visited[x][y] = true;
    edges[x].push_back(y);
    inDegree[y]++;
    return false;
}

int topSort() { //拓扑排序
    queue<int> q;
    memset(copyInDegree, 0, sizeof copyInDegree); //每次拓扑后入度不能被修改呢
    for (int i = 0; i < n; i++) {
        if (inDegree[i] == 0) q.push(i);
        copyInDegree[i] = inDegree[i];
    }
    ans.clear();
    bool inc = false;
    while (!q.empty()) {
        if(q.size() > 1) inc = true;
        int x = q.front();
        ans.push_back(x);
        q.pop();
        for(int i=0;i<edges[x].size();i++){
            int y = edges[x][i];
            if (--copyInDegree[y] == 0) {
                q.push(y);
            }
        }
    }
    if(ans.size() < n) return 2;
    if(inc) return 3;
    return 1;
}

int main() {
    scanf("%d %d", &n, &m);
    while (n != 0 || m != 0) {
        memset(inDegree, 0, sizeof inDegree);
        memset(visited, 0, sizeof visited);
        memset(edges, 0, sizeof edges);
        bool skip = false;
        int t = 0, result = 3;
        for (int i = 1; i <= m; i++) {
            char input[4] = {0};
            scanf("%s", input);
            if (addEdge(input[0] - 'A', input[2] - 'A')) continue;
            if (skip) continue; //跳过也得读完呐...
            result = topSort();
            t++;
            if (result == 3) continue; //无解了
            skip = true; //冲突和求出唯一解是只需判断一次的，后面直接跳过即可
        }
        if (result == 1) {
            printf("Sorted sequence determined after %d relations: ", t);
            for (int i = 0; i < ans.size(); i++) printf("%c", ans[i] + 'A');
            printf(".\n");
        } else if (result == 2) printf("Inconsistency found after %d relations.\n", t);
        else printf("Sorted sequence cannot be determined.\n");
        scanf("%d %d", &n, &m);
    }
}

找个时间写写floyd的思路