<p>You have information about <code>n</code> different recipes. You are given a string array <code>recipes</code> and a 2D string array <code>ingredients</code>. The <code>i<sup>th</sup></code> recipe has the name <code>recipes[i]</code>, and you can <strong>create</strong> it if you have <strong>all</strong> the needed ingredients from <code>ingredients[i]</code>. Ingredients to a recipe may need to be created from <strong>other </strong>recipes, i.e., <code>ingredients[i]</code> may contain a string that is in <code>recipes</code>.</p>

<p>You are also given a string array <code>supplies</code> containing all the ingredients that you initially have, and you have an infinite supply of all of them.</p>

<p>Return <em>a list of all the recipes that you can create. </em>You may return the answer in <strong>any order</strong>.</p>

<p>Note that two recipes may contain each other in their ingredients.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> recipes = [&quot;bread&quot;], ingredients = [[&quot;yeast&quot;,&quot;flour&quot;]], supplies = [&quot;yeast&quot;,&quot;flour&quot;,&quot;corn&quot;]
<strong>Output:</strong> [&quot;bread&quot;]
<strong>Explanation:</strong>
We can create &quot;bread&quot; since we have the ingredients &quot;yeast&quot; and &quot;flour&quot;.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> recipes = [&quot;bread&quot;,&quot;sandwich&quot;], ingredients = [[&quot;yeast&quot;,&quot;flour&quot;],[&quot;bread&quot;,&quot;meat&quot;]], supplies = [&quot;yeast&quot;,&quot;flour&quot;,&quot;meat&quot;]
<strong>Output:</strong> [&quot;bread&quot;,&quot;sandwich&quot;]
<strong>Explanation:</strong>
We can create &quot;bread&quot; since we have the ingredients &quot;yeast&quot; and &quot;flour&quot;.
We can create &quot;sandwich&quot; since we have the ingredient &quot;meat&quot; and can create the ingredient &quot;bread&quot;.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> recipes = [&quot;bread&quot;,&quot;sandwich&quot;,&quot;burger&quot;], ingredients = [[&quot;yeast&quot;,&quot;flour&quot;],[&quot;bread&quot;,&quot;meat&quot;],[&quot;sandwich&quot;,&quot;meat&quot;,&quot;bread&quot;]], supplies = [&quot;yeast&quot;,&quot;flour&quot;,&quot;meat&quot;]
<strong>Output:</strong> [&quot;bread&quot;,&quot;sandwich&quot;,&quot;burger&quot;]
<strong>Explanation:</strong>
We can create &quot;bread&quot; since we have the ingredients &quot;yeast&quot; and &quot;flour&quot;.
We can create &quot;sandwich&quot; since we have the ingredient &quot;meat&quot; and can create the ingredient &quot;bread&quot;.
We can create &quot;burger&quot; since we have the ingredient &quot;meat&quot; and can create the ingredients &quot;bread&quot; and &quot;sandwich&quot;.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>n == recipes.length == ingredients.length</code></li>
	<li><code>1 &lt;= n &lt;= 100</code></li>
	<li><code>1 &lt;= ingredients[i].length, supplies.length &lt;= 100</code></li>
	<li><code>1 &lt;= recipes[i].length, ingredients[i][j].length, supplies[k].length &lt;= 10</code></li>
	<li><code>recipes[i], ingredients[i][j]</code>, and <code>supplies[k]</code> consist only of lowercase English letters.</li>
	<li>All the values of <code>recipes</code> and <code>supplies</code>&nbsp;combined are unique.</li>
	<li>Each <code>ingredients[i]</code> does not contain any duplicate values.</li>
</ul>

class Solution:
    def findAllRecipes(self, recipes: List[str], ingredients: List[List[str]], supplies: List[str]) -> List[str]:
    
    # # basic recipes and composite recipes
    # # nested recipes:
    # # add can_create recipes to supplies
    # # if all missing ingredients are in recipes, 
    # #   track which are needed
    # #   how? reverse index? ingredient to recipe? 
    #     # but what if multiple imgredients are no_type_check_decorator(
    # # dependency graph bw recipes?
    # # create graph of recipes, directional edge (v1, v2) means you need v2 to make v1
    # # how to traverse strating with nodes with no edges?
    # # heapq? process by node val (#edges) and add to supplies

    # # need to somehow propagate dependencies, cycles? 

    #     supplies = set(supplies)
    #     recipes_set = set(recipes)
    #     heap = []
    #     for i, recipe in enumerate(recipes):
    #         have_all_basic = True
    #         dependencies = []
    #         for ingredient in ingredients[i]:
    #             if ingredient not in supplies:
    #                 if ingredient in recipes_set:
    #                     dependencies.append(ingredient)
    #                 else:
    #                     have_all_basic = False
    #         if have_all_basic:
    #             heap.append((len(dependencies), recipe, dependencies))
    #     can_create = set()
    #     heapq.heapify(heap)
    #     while heap:
    #         _ , recipe, dependencies = heapq.heappop(heap)
    #         have_all = True
    #         for ingredient in dependencies:
    #             if ingredient not in can_create:
    #                 have_all = False
    #         if have_all:
    #             can_create.add(recipe)            
    #     return list(can_create)

         # Construct directed graph and count the in-degrees
        ingredient_to_recipe, in_degree = defaultdict(set), Counter()
        for rcp, ingredient in zip(recipes, ingredients):
            for ing in ingredient:
                ingredient_to_recipe[ing].add(rcp)
            in_degree[rcp] = len(ingredient)

        print(ingredient_to_recipe)
        # Topological sort.    
        available, ans = deque(supplies), []
        while available:
            ing = available.popleft()
            # for rcp in ingredient_to_recipe.pop(ing, set()):
            for rcp in ingredient_to_recipe[ing]:
                # ingredient_to_recipe[ing].remove(rcp)
                in_degree[rcp] -= 1
                if in_degree[rcp] == 0:
                    available.append(rcp)
                    ans.append(rcp)
        return ans
20300