An interesting topological sort algorithm

2115. Find All Possible Recipes from Given Supplies

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.

Time complexity:

The worst case each time we find one recipe. The total complexity will be

O(sizeof(recipes)*sizeof(recipes)*sizeof( ingredient)) = O(100³) based on the data size.

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

Usually the topological sort needs the initial nodes has zero indegree. For this problem, it is not necessary. This makes it special.

The topological sort has the complexity of O(V + E). For this problem, the V is at most 200, and E is at most V². So the overrall complexity is about O(V²).

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