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

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @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
        if numFruits == 0:
            return []
        if numFruits == 1:
            return [[0]]
        pre_dict = dict()
        for pre in prerequisites:
            if pre[0] in pre_dict:
                pre_dict[pre[0]].add(pre[1])
            else:
                pre_dict[pre[0]] = set()
                pre_dict[pre[0]].add(pre[1])

        ans = []

        def dfs(pre_order: list, used: set, unused: list, requirement: dict):
            if len(pre_order) == numFruits:
                ans.append(pre_order)
                return
            for i, f in enumerate(unused):
                if not f in requirement or requirement[f] <= used:
                    dfs(
                        pre_order + [f],
                        used | set([f]),
                        unused[:i] + unused[i + 1 :],
                        requirement,
                    )
            return

        dfs([], set(), list(range(numFruits)), pre_dict)
        ans.sort()
        return ans