<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>

#  ith recipe name
#  ith array of ingredients needed for ith recipe

# -> ingredients can be recipe

# supplies containing all the ingredients that you have,  infinite supply of all 
# -> can reuse supply as many time as needed

# Return a list of all the recipes that you can create. You may return the answer in any order.
# -> return a list of string being the name of the recipes you can create given the supply ypu have

# -> to create a recipe you need ingredients
#     -> ingredients can be supplies
#     -> ingredients can be recipes -> which have ingredients -> which need supplies

#     -> if ingredient is not in supply
#         -> is it in recipe?
#         -> if yes -> do we have ingredients for recipe
    

# Note that two recipes may contain each other in their ingredients
# -> loop can recipes ingredients be in supply?
# -> banana bread needs banana cake
# -> banana cake needs banana bread
# --> loop so both banana cake and bread can't be made 


# 1 <= n <= 100 -> can be up to 100 recipes -> medium size input 

# supplies/ ingredient list length is medium size

# name of recipe and ingredients are between 1 to 10 lowercase char

# All the values of recipes and supplies combined are unique.
# -> meaning recipes can't be supply ingredients

# no ingredient duplicate in list of ingredients for recipe





class Solution:
    def findAllRecipes(self, recipes: List[str], ingredients: List[List[str]], supplies: List[str]) -> List[str]:


        # topological sort
        
        #
        # supplies

        recipe_graph = {}
        recipe_set = set( recipe for recipe in recipes)
        supply_set = set(supply for supply in supplies)

        for i,recipe in enumerate(recipes):
            # get each ingredients list
            recipe_graph[recipe] = ingredients[i]
        
        visiting = set()

        def isCookable(recipe) -> bool:
            
            if recipe in visiting:
                return False

            if recipe in supply_set:
                return True
            
            visiting.add(recipe)
            
            for ingredient in recipe_graph[recipe]:

                if ingredient not in supply_set:
                    
                    if ingredient not in recipe_set or not isCookable(ingredient):
                        return False

        
            visiting.remove(recipe)
            supply_set.add(recipe)
            return True
        res = []
        for recipe in recipes:
            if isCookable(recipe):
                res.append(recipe)

        return res        
                



        
744