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