算法分析

floyd解决传递闭包问题，核心思想:i --> k且k --> j，则i -- > j

• 情况1、矛盾，d[i,i] = 1;

• 情况2、唯一确定，对于所有i != j,且d[i,j]和d[j,i]有且只有一个均成立

• 情况3、顺序不唯一

当所有的关系大小均确定的时候，需要从小到大输出字母编号，调用getSequence()输出，由于已经传递闭包过，因此所有的关系已经确定，对于闭包后的每一对关系，假设A > B,因此A的等级就加1，遍历所有传递闭包后的关系，对相应的等级进行累加，再对等级大小进行排序，等级越大的字母大小关系也越大

注意：题目说到从前往后遍历每对关系，每次遍历时判断，因此每一次新增一关系都得做floyd和check()判断

时间复杂度

参考文献

算法提高课

Java 代码

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    static int N = 26;
    static int[][] g = new int[N][N];
    static int[][] dist = new int[N][N];
    static int n,m;
    static Pair[] level = new Pair[N];
    static void floyd()
    {
        dist = g.clone();
        for(int k = 0;k < n;k ++)
            for(int i = 0;i < n;i ++)
                for(int j = 0;j < n;j ++)
                {
                    if(dist[i][k] == 1 && dist[k][j] == 1)
                    {
                        dist[i][j] = 1;
                    }
                }
    }
    static int check()
    {
        for(int i = 0;i < n;i ++) if(dist[i][i] == 1) return 2;
        for(int i = 0;i < n;i ++)
            for(int j = 0;j < i;j ++)
            {
                if((dist[i][j] == 0 && dist[j][i] == 0)) return 0;
            }

        return 1;
    }
    static String getSequence()
    {
        for(int i = 0;i < n;i ++) level[i] = new Pair((char)('A' + i),0);

        for(int i = 0;i < n;i ++)
            for(int j = 0;j < i;j ++)
            {
                //dist[i][j]不为1，对称的一边一定为1
                if(dist[i][j] == 1) level[j].d ++;
                else level[i].d ++;
            }

        Arrays.sort(level,0,n);

        String res = "";
        for(int i = 0;i < n;i ++)
        {
            res += level[i].c;
        }
        return res;
    }
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        while(true)
        {
            n = scan.nextInt();
            m = scan.nextInt();
            if(n == 0 && m == 0) break;
            for(int i = 0;i < n;i ++) Arrays.fill(g[i],0);
            int type = 0,t = 0; // type - 0：不确定，1：唯一确定，2：矛盾
            while(m -- > 0)
            {
                char[] charArray = scan.next().toCharArray();
                if(type > 0) continue;

                int a = charArray[0] - 'A', b = charArray[2] - 'A';
                g[a][b] = 1;//表示a < b

                floyd();

                type = check();
                t ++;
            }
            if (type == 0) System.out.println("Sorted sequence cannot be determined.");
            else if (type == 2) System.out.println("Inconsistency found after " + t + " relations.");
            else 
            {
                System.out.println("Sorted sequence determined after " + t + " relations: " + getSequence() + ".");
            }
        }
    }
}
class Pair implements Comparable<Pair>
{
    char c ;//当前字符
    int d;
    Pair(char c,int d)
    {
        this.c = c;
        this.d = d;
    }
    @Override
    public int compareTo(Pair o) {
        // TODO 自动生成的方法存根
        return Integer.compare(d, o.d);
    }
}