343 排序（floyd算法求解传递闭包）

本文主要是介绍343 排序（floyd算法求解传递闭包），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

1. 问题描述：

给定 n 个变量和 m 个不等式。其中 n 小于等于 26，变量分别用前 n 的大写英文字母表示。不等式之间具有传递性，即若 A > B 且 B > C，则 A > C。
请从前往后遍历每对关系，每次遍历时判断：
如果能够确定全部关系且无矛盾，则结束循环，输出确定的次序；
如果发生矛盾，则结束循环，输出有矛盾；
如果循环结束时没有发生上述两种情况，则输出无定解。

输入格式

输入包含多组测试数据。每组测试数据，第一行包含两个整数 n 和 m。接下来 m 行，每行包含一个不等式，不等式全部为小于关系。当输入一行 0 0 时，表示输入终止。

输出格式

每组数据输出一个占一行的结果。结果可能为下列三种之一：
如果可以确定两两之间的关系，则输出 "Sorted sequence determined after t relations: yyy...y.",其中't'指迭代次数，'yyy...y'是指升序排列的所有变量。
如果有矛盾，则输出： "Inconsistency found after t relations."，其中't'指迭代次数。
如果没有矛盾，且不能确定两两之间的关系，则输出 "Sorted sequence cannot be determined."。

数据范围

2 ≤ n ≤ 26，变量只可能为大写字母 A∼Z。

输入样例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

输出样例1：

Sorted sequence determined after 4 relations: ABCD.
Inconsistency found after 2 relations.
Sorted sequence cannot be determined.

输入样例2：

6 6
A<F
B<D
C<E
F<D
D<E
E<F
0 0

输出样例2：

Inconsistency found after 6 relations.

输入样例3：

5 5
A<B
B<C
C<D
D<E
E<A
0 0

输出样例3：

Sorted sequence determined after 4 relations: ABCDE.
来源：https://www.acwing.com/problem/content/description/345/

2. 思路分析：

3. 代码如下：

from typing import List


class Solution:
    # 使用floyd算法将所有间接可以到达的点直接连起来
    def floyd(self, n: int, dis: List[List[int]]):
        for k in range(n):
            for i in range(n):
                for j in range(n):
                    # 通过中间点k能够使得i与j之间联通那么可以将i到j连一条边
                    dis[i][j] |= 1 if dis[i][k] and dis[k][j] else 0

    def check(self, n: int, dis: List[List[int]]):
        for i in range(n):
            # A < A所以是矛盾的
            if dis[i][i] == 1:
                return 2
        for i in range(n):
            for j in range(i):
                # 不能够确定具体的所有节点的大小关系, 需要任意两点之间都是存在边的
                if dis[i][j] == 0 and dis[j][i] == 0:
                    return 0
        # 执行到这里说明任意两个点之间是存在边的
        return 1
    
    # 求解当前确定小于号关系的各个节点的顺序
    def getMin(self, n: int, sta: List[int], dis: List[List[int]]):
        for i in range(n):
            if sta[i] == 0:
                flag = 1
                for j in range(n):
                    # 说明反向是存在边的也即当前的点事不满足条件的
                    if sta[j] == 0 and dis[j][i] == 1:
                        flag = 0
                        break
                # 当前的节点是满足条件的这个时候需要标记一下并且返回对应的大写字母
                if flag:
                    sta[i] = 1
                    return chr(65 + i)

    def process(self):
        while True:
            n, m = map(int, input().split())
            if n == 0 and m == 0: break
            dis = [[0] * n for i in range(n)]
            # 记录当前的类型
            type, t = 0, 0
            for i in range(1, m + 1):
                s = input()
                a, b = ord(s[0]) - ord("A"), ord(s[2]) - ord("A")
                if type == 0:
                    dis[a][b] = 1
                    self.floyd(n, dis)
                    type = self.check(n, dis)
                    if type:
                        t = i
            if type == 0:
                print("Sorted sequence cannot be determined.")
            elif type == 2:
                print("Inconsistency found after {:} relations.".format(t))
            else:
                sta = [0] * n
                print("Sorted sequence determined after {:} relations: ".format(t), end="")
                for i in range(n): print(self.getMin(n, sta, dis), end="")
                print(".")


if __name__ == "__main__":
    Solution().process()

这篇关于343 排序（floyd算法求解传递闭包）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！