一 原问题链接

Sorting It All Out - POJ 1094 - Virtual Judge

https://vjudge.net/problem/POJ-1094

二 输入和输出

1 输入

输入包含多个测试用例。每个测试用例的第 1 行都包含两个正整数 n 和 m。n 表示要排序的对象数量，排序的对象是大写字母的前 n 个字符。m 表示给出的 A<B 形式的关系数量。接下来的 m 行，每行都包含一种由 3 个字符组成的关系：第 1 个大写字母、字符 < 和第 2 个大写字母。n=m=0的值表示输入结束。

2 输出

对于每个问题实例，其输出都由一行组成，该行应该是以下三种之一。

• 在 x 种关系之后确定的排序顺序：yyy..y。
• 无法确定排序顺序。
• 在 x 种关系后发现不一致。

其中，x 是在确定排序序列或找到不一致时处理的关系数，以先到者为准，yyy...y 是已排序的升序序列。

三 输入和输出样例

1 输入样例

4 6

A<B

A<C

B<C

C<D

B<D

A<B

3 2

A<B

B<A

26 1

A<Z

0 0

2 输出样例

Sorted sequence determined after 4 relations: ABCD.

Inconsistency found after 2 relations.

Sorted sequence cannot be determined.

四 分析

本问题中，一边进行输入，一边进行判断，分为有序、无序、无法确定三种情况，可以利用拓扑排序进行判断。

五  算法设计

1 如果入度为 0 的节点个数为 0，则说明有环；如果拓扑序列节点数小于 n，则也说明有环。此情况无序。

2 如果入度为 0 的节点个数大于1，则无法确定，因为拓扑排序不唯一。

3 否则是拓扑有序，输入拓扑序列。

六 代码

package graph.poj3687;

import java.util.Scanner;
import java.util.Stack;

public class Poj1094 {
    static final int maxn = 27;
    static int map[][];
    static int indegree[];
    static int topo[];
    static int temp[];
    static int n;
    // flag=1:有序 flag=-1:不确定
    static int flag;
    static Stack<Integer> s = new Stack<>();

    static int TopoSort(int n) { //拓扑排序
        flag = 1;
        for (int i = 1; i <= n; i++)
            temp[i] = indegree[i];//一边输入一边拓扑排序，所有入度数组不能改变
        int m = 0, cnt = 0;
        for (int i = 1; i <= n; i++)//查找入度为零的顶点个数，若>1，拓扑序不确定
            if (temp[i] == 0) {
                s.push(i);
                cnt++;
            }
        if (cnt == 0) return 0; //有环
        if (cnt > 1) flag = -1; //不确定
        while (!s.empty()) {
            cnt = 0;
            int i = s.peek();
            s.pop();
            topo[m++] = i;
            for (int j = 1; j <= n; j++)
                if (map[i][j] == 1) {
                    temp[j]--;
                    if (temp[j] == 0) {
                        s.push(j);
                        cnt++;
                    }
                }
            if (cnt > 1) flag = -1;//不确定
        }
        if (m < n)//有环
            return 0;
        return flag;
    }

    public static void main(String[] args) {
        int m, n;
        boolean sign; // 当sign = true 时，已得出结果
        String str;
        Scanner scanner = new Scanner(System.in);
        while (true) {
            map = new int[maxn][maxn];
            indegree = new int[maxn];
            topo = new int[maxn];
            temp = new int[maxn];
            n = scanner.nextInt();
            m = scanner.nextInt();
            if (m == 0 && n == 0) break;

            sign = false;
            for (int i = 1; i <= m; i++) {
                str = scanner.next();
                if (sign) continue; //一旦得出结果，对后续的输入不做处理
                int x = str.charAt(0) - 'A' + 1;
                int y = str.charAt(2) - 'A' + 1;
                map[x][y] = 1;
                indegree[y]++;
                int s = TopoSort(n);
                if (s == 0) { // 有环
                    System.out.printf("Inconsistency found after %d relations.\n", i);
                    sign = true;
                } else if (s == 1) { //有序
                    System.out.printf("Sorted sequence determined after %d relations: ", i);
                    for (int j = 0; j < n; j++)
                        System.out.print((topo[j] + 'A' - 1));
                    System.out.printf(".\n");
                    sign = true;
                }
            }
            if (!sign) // 不确定
                System.out.print("Sorted sequence cannot be determined.\n");
        }
    }
}

七 测试