Problem URL: Find all possible recipes from given supplies

We will create a graph where each node represents a recipe and each edge represents a supply. We will iterate over the recipes and add the edges to the graph. We will use topological sort to solve the dependencies in the graph. We will iterate over the supplies and check if the supply is in the graph or not. If it is not, we can return an empty list. If it is, we can add the recipes to the result. Finally, we will return the result.

class Solution:
    def findAllRecipes(self, recipes: List[str], ingredients: List[List[str]], supplies: List[str]) -> List[str]:
        res = []
        q = deque(supplies)
        graph = defaultdict(list) 
        degree = defaultdict(int)

        for recipe, items in  zip(recipes, ingredients):
            degree[recipe] = len(items) 
            for item in items: graph[item].append(recipe)

        while q:
            ing = q.pop()
            for recipe in graph[ing]:
                degree[recipe] -= 1
                if degree[recipe] == 0:
                    q.appendleft(recipe)
                    res.append(recipe)
        return res

Time complexity: O(n)
Space complexity: O(n)