# 2115. Find All Possible Recipes from Given Supplies

```
T: O(V+E)
S: O(n*m + m), ingredients: n, recipes: m
```

```java
class Solution {
    public List<String> findAllRecipes(String[] recipes, List<List<String>> ingredients, String[] supplies) {
        Map<String, List<String>> graph = new HashMap<>();
        Map<String, Integer> indegree = new HashMap<>();
        Set<String> recipesSet = new HashSet<>();
        
        for (int i = 0; i < recipes.length; i++) {
            recipesSet.add(recipes[i]);
            for (int j = 0; j < ingredients.get(i).size(); j++) {
                String from = ingredients.get(i).get(j);
                String to = recipes[i];
                
                graph.putIfAbsent(from, new ArrayList<>());
                graph.get(from).add(to);
                
                indegree.put(to, indegree.getOrDefault(to, 0)+1);
            }
        }
        
        // this question's begin is using supplies
        Queue<String> queue = new LinkedList<>();
        for (String supply : supplies) {
            queue.offer(supply);
        }
        
        List<String> res = new ArrayList<>();
        while (!queue.isEmpty()) {
            String from = queue.poll();
            if (recipesSet.contains(from)) {
                res.add(from);
            }
            for (String to : graph.getOrDefault(from, new ArrayList<>())) {
                indegree.put(to, indegree.get(to) - 1);
                if (indegree.get(to) == 0) {
                    queue.offer(to);
                }
            }
        }
        return res;
    }
}

/*

recipes = ["bread","sandwich"], ingredients = [["yeast","flour"],["bread","meat"]]
supplies = ["yeast","flour","corn"]


"yeast", \bread
"flour" /     \  sandwich
          meat/      
          
supplies = ["yeast","flour","meat"] => indegree = 0


"yeast"   bread   sandwich   burger
"flour"   meat    meat
                  bread
                  
use topology sort:

ingredients: from
recipes: to
supplies: are the begins

T: O(V+E)
S: O(n*m + m), ingredients: n, recipes: m
*/
```

better one:

```java
class Solution {
    public List<String> findAllRecipes(String[] recipes, List<List<String>> ingredients, String[] supplies) {
        Set<String> recipeSet = new HashSet<>();
        Map<String, Integer> indegree = new HashMap<>();
        Map<String, List<String>> graph = buildGraph(recipes, ingredients, indegree, recipeSet);
        
        Queue<String> queue = new LinkedList<>();
        for (String supply : supplies) {
            queue.offer(supply);
        }
        List<String> result = new ArrayList<>();
        while (!queue.isEmpty()) {
            String cur = queue.poll();
            if (recipeSet.contains(cur)) {
                result.add(cur);
            }
            for (String next : graph.getOrDefault(cur, new ArrayList<>())) {
                indegree.put(next, indegree.getOrDefault(next, 0)-1);
                if (indegree.get(next) == 0) {
                    queue.offer(next);
                }
            }
        }
        return result;
    }
    private Map<String, List<String>> buildGraph(String[] recipes, List<List<String>> ingredients, Map<String, Integer> indegree, Set<String> recipeSet) {
        Map<String, List<String>> graph = new HashMap<>();
        for (int i = 0; i < recipes.length; i++) {
            String to = recipes[i];
            recipeSet.add(to);
            for (String from : ingredients.get(i)) {
                graph.putIfAbsent(from, new ArrayList<>());
                graph.get(from).add(to);
                
                indegree.put(to, indegree.getOrDefault(to, 0) + 1);
            }
        }
        return graph;
    }
}

/*

["yeast","flour"] -> "bread"
                     ["bread","meat"] -> sandwich
           
           s
        "yeast"
         "flour"    -> "bread"  -> sandwich       
                        "meat"
                          s
                          
      bread indree is 2
      sandwich is 2
      
      so when bread, sandwich indegree == 0 -> means we can arrive, 
      and we'll check when something arrive, is it existed in recipes 
      
      T: build graph: ingredients*recipes + supplies + topology sort O(V+E)
                          
*/
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://timmybeeflin.gitbook.io/cracking-leetcode/topology/2115.-find-all-possible-recipes-from-given-supplies.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.