# Naively find until can not find any new recipe

• If we find a new recipe, then add it to the supplies.
• Repeat this process until no new recipe can be found.
`class Solution {public:bool good_to_go(vector<string>&ingredients, unordered_set<string> & supplies){    for (auto & ingredient: ingredients){        if (supplies.find(ingredient) == supplies.end()){            return false;        }    }    return true;}    vector<string> findAllRecipes(vector<string>& recipes, vector<vector<string>>& ingredients, vector<string>& supplies) {        vector<string> ret;        unordered_set<string> supplies_(supplies.begin(), supplies.end());        bool found_new = true;        vector<int> unfound_idx;        for(int i = 0; i < recipes.size();++i)unfound_idx.push_back(i);        while (found_new){            found_new = false;            vector<int> new_unfound_idx;            for (auto idx: unfound_idx){                if (good_to_go(ingredients[idx], supplies_ )){                    found_new = true;                    ret.push_back(recipes[idx]);                    supplies_.insert(recipes[idx]);                } else {                    new_unfound_idx.push_back(idx);                }            }            unfound_idx = new_unfound_idx;        }        return ret;    }};`

# Based on topological sort

`class Solution {public:    vector<string> findAllRecipes(vector<string>& recipes, vector<vector<string>>& ingredients, vector<string>& supplies) {        vector<string> ret;        unordered_map<string, vector<string>> graph;        const int n = recipes.size();        unordered_map<string, int> indegrees;        for (int i = 0; i < n; ++i){            auto recipe = recipes[i];            auto ingredient = ingredients[i];            for (auto &x: ingredient){                graph[x].push_back(recipe);                indegrees[recipe]++;            }        }        unordered_set<string> recipes_(recipes.begin(), recipes.end());        // directly initializing the queue will get an error.        //queue<string> Q(supplies.begin(), supplies.end());        queue<string> Q(deque<string>(supplies.begin(), supplies.end()));        while (!Q.empty()){            auto supply = Q.front(); Q.pop();            if (recipes_.find(supply) != recipes_.end()){                ret.push_back(supply);            }            for (auto &nei: graph[supply]){                indegrees[nei]--;                if (indegrees[nei] == 0){                    Q.push(nei);                }            }        }        return ret;    }};`

--

--

--

## More from Jimmy Shen

Data Scientist/MLE/SWE @takemobi

Love podcasts or audiobooks? Learn on the go with our new app.

## Jimmy Shen

Data Scientist/MLE/SWE @takemobi