leetcode：剑指 Offer II 115. 重建序列【图论思维 + 入度考虑 + 拓扑排序】

分析

这种子序列的有严格的先后顺序，可考虑成边
然后进行拓扑排序，看看是否唯一
对sequences的相邻两点，我们可以存边和计算入度
然后建一个queue，放入入度为0的
显然，只能有一个入度为0的，否则多种选择
然后对于queue中的，我们找他的下一个点，入度为1的
这些入度为1的必须紧跟在后面，而且只能有1个，否则面临多种选择。。。

ac code

class Solution:
    def sequenceReconstruction(self, nums: List[int], sequences: List[List[int]]) -> bool:
        # 关于图论和入度
        n = len(nums)
        inDeg = [inf] + [0] * n
        g = defaultdict(list)

        for sequence in sequences:
            for x, y in pairwise(sequence):
                g[x].append(y)
                inDeg[y] += 1
        
        # q存入度为0的
        q = deque([i for i, degrees in enumerate(inDeg) if degrees == 0])

        while q:
            # 多个选择
            if len(q) > 1:
                return False
            
            x = q.popleft()
            for y in g[x]:
                degree = inDeg[y]
                if inDeg[y] == 1:
                    #inDeg[y] -= 1
                    q.append(y)

        return True

总结

顺序问题转成图论的拓扑排序问题
考虑入度为1的只能选一个