Find All Possible Recipes from Given Supplies LeetCode solution in C++

1
class Solution {
2
 public:
3
  vector<string> findAllRecipes(vector<string> &recipes, vector<vector<string>> &ingredients,
4
                                vector<string> &supplies) {
5
    unordered_map<string, int> indegree;
6
    for (auto i : recipes) indegree[i] = 0; // Initially indegree of every recipe is 0
7

8
    unordered_map<string, vector<string>> graph;
9

10
    for (int i = 0; i < recipes.size(); i++) {
11
      for (int j = 0; j < ingredients[i].size(); j++) {
12
        if (find(supplies.begin(), supplies.end(), ingredients[i][j]) ==
13
            supplies.end()) { // finds if the ingredient exist in the supply or not
14

15
          graph[ingredients[i][j]].push_back(recipes[i]); // If not then ingredients[i][j] is
16
                                                          // required to prepare the recipes[i] i.e
17
                                                          // bread--->burger, sandwitch ---> burger
18

19
          indegree[recipes[i]]++; // increase the indegree of the recipe , for
20
                                  // example , bread->burger,sandwitch-->burger
21
                                  // , now indegree of burger is 2
22
        }
23
      }
24
    }
25
    queue<string> q; // Now simple topo sort using bfs (Kahn's algorithm)
26
    for (auto i : indegree) {
27
      if (i.second == 0) q.push(i.first);
28
    }
29
    vector<string> ans;
30

31
    while (!q.empty()) {
32
      string front = q.front();
33
      q.pop();
34
      ans.push_back(front);
35
      for (auto i : graph[front]) {
36
        indegree[i]--;
37
        if (!indegree[i]) q.push(i);
38
      }
39
    }
40
    return ans;
41
  }
42
};