题解 | #牛牛吃水果的顺序#

from sys import float_repr_style
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param numFruits int整型 
# @param prerequisites int整型二维数组 
# @return int整型二维数组
#
class Solution:
    def findFruitOrder(self , numFruits: int, prerequisites: List[List[int]]) -> List[List[int]]:
        # write code here
        # 找出所有符合要求的顺序
        # 用一个q来记录下一个要吃的水果
        ans = []
        visited = set()
    
        n = numFruits
        # 用字典来存储prereq，方便查询
        prev = dict()
        for idx, req in prerequisites:
            if idx not in prev:
                prev[idx] = [req]
            else:
                prev[idx].append(req)
        # 用dfs记录path
        try_visited = set()
        def dfs(idx, path, left): #
            temp = str(idx) + str(path) + str(left)
            if temp in try_visited:
                return # 已经访问过了
            try_visited.add(temp) # 记录这次访问
            # print(temp)
            if len(left) == 0:
                ans.append(path.copy())
                return 
            
            # check idx
            pre = prev.get(idx, []) # 前置点
            path_set = set(path)
            left_pre = []
            for ele in pre:
                if ele in path_set: # 已经满足了
                    continue
                else:
                    left.remove(ele) # 先移除，后面放到前面
                    left_pre.append(ele) # 尚未满足

            left = left_pre + left # 重新排序
            
            if len(left_pre) == 0: # 如果前置都满足了，该点可以加入了
                path.append(idx)
                left.remove(idx)
                if not left:
                    dfs(-1, path, left) # 只用记录
                else: # 进行下一个点的check
                    for i in range(len(left)):
                        next_id = left[i]
                        dfs(next_id, path, left.copy()) # 进一步， 需要用copy，因为left会remove
                # clean
                path.remove(idx)
                left.append(idx)
            else: # 有前置条件不满足，先满足前置点
                # 调整left顺序后，重新检查
                for ii in left_pre:
                    dfs(ii, path, left) # redirect
                return
        
        dfs(0, [], list(range(n)))
        return ans

需要记录path，所以用dfs。每次检查所有前置点是否满足，如果不满足则调整执行顺序。感觉还有很大优化空间。