说实话这题应该放在图论1题单里面

题面

约定输入为 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(cpp)代码

#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);
    }
}

大佬帮纠正，谢谢。