---
tags: leetcode
---

# [2115. Find All Possible Recipes from Given Supplies](https://leetcode.com/problems/find-all-possible-recipes-from-given-supplies/)
---
# My Solution
## The Key Idea for Solving This Coding Question
Topological Sort
## C++ Code

class Solution {
public:
    vector<string> findAllRecipes(vector<string> &recipes, 
                                  vector<vector<string>> &ingredients, 
                                  vector<string> &supplies) {
        unordered_map<string, vector<string>> graph;
        unordered_map<string, int> indegree;
        for (int i = 0; i < recipes.size(); ++i) {
            for (int j = 0; j < ingredients[i].size(); ++j) {
                graph[ingredients[i][j]].push_back(recipes[i]);
                ++indegree[recipes[i]];
            }
        }

        queue<string> q;
        for (int i = 0; i < supplies.size(); ++i) {
            q.push(supplies[i]);
        }

        vector<string> answer;

        while (!q.empty()) {
            string item = q.front();
            q.pop();

            for (auto &recipe : graph[item]) {
                --indegree[recipe];
                if (indegree[recipe] == 0) {
                    q.push(recipe);
                    answer.push_back(recipe);
                }
            }
        }

        return answer;
    }
};

## Time Complexity
## Space Complexity
# Miscellaneous
[210. Course Schedule II](https://leetcode.com/problems/course-schedule-ii/)
<!--
# Test Cases

["bread"]
[["yeast","flour"]]
["yeast","flour","corn"]

["bread","sandwich"]
[["yeast","flour"],["bread","meat"]]
["yeast","flour","meat"]

["bread","sandwich","burger"]
[["yeast","flour"],["bread","meat"],["sandwich","meat","bread"]]
["yeast","flour","meat"]

* Wrong Answer:
https://leetcode.com/submissions/detail/693404063/
* Runtime Error:
https://leetcode.com/problems/find-all-possible-recipes-from-given-supplies/submissions/837936330/
-->