An interesting topological sort algorithm

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;
}
};

--

--

--

Data Scientist/MLE/SWE @takemobi

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

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Jimmy Shen

Jimmy Shen

Data Scientist/MLE/SWE @takemobi

More from Medium

Why should we study algorithms? — [Introduction to Algorithms]

Time and Space Complexity — P1

Spotify — Genres Network Analysis

7. Connecting the dots — Big O and Hash Table Data Structure