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

刺骨的言语ヽ痛彻心扉 2022-09-17 03:01 142阅读 0赞

**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/][https_www.acwing.com_problem_content_description_345]

**2. 思路分析：**

分析题目可以知道我们需要求解有向图中的传递闭包，可以使用**floyd算法**来求解传递闭包；其实传递闭包求解的思路还是比较好理解的，给我们一个有向图（无向图可以看成是特殊的有向图），我们可以将所有间接可以到达的两个点给他们连上一条边，floyd算法可以在O(n ^ 3)的时间复杂度求解原图的传递闭包，求解传递闭包的时候只需要在floyd算法求解任意两点的最短距离修改为：如果i~k有路径可以到达，并且k~j有路径可以到达，那么可以将i到j连上一条边，也即dis\[i\]\[j\] = 1，当dis\[i\]\[j\] = 0时表示i与j之间不可直接到达；我们在实际做的时候可以每连一条边，判断一下连上边之后是否存在矛盾，或者可以确定所有节点的小于关系，或者不能确定所有节点的大小关系，使用一个变量type来存储当前连上边之后的类型，0表示不确定，1表示可以确定所有节点编号的小于关系，2表示存在矛盾，矛盾的意思是 A > B，B > A == > A > A，也即自己到自己有一条边就是存在矛盾的。还需要解决的一个问题是当小于关系确定之后如何输出节点编号对应的顺序，我们可以借助一个标记数组sta来标记已经输出的节点编号，从前往后找到第一个没有被标记而且到其他所有节点都有边的节点编号返回即可；

**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记录当前连上边之后的类型
                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()

[https_www.acwing.com_problem_content_description_345]: https://www.acwing.com/problem/content/description/345/