Leetcode-2115: find all the dishes that can be made from the given raw materials

subject

Topic linking

Do you have n Information about different dishes . Here's an array of strings recipes And a two-dimensional string array ingredients . The first i The name of this dish is recipes[i] , If you have it all Raw materials ingredients[i] , Then you can To make a This dish . The raw material of a dish may be Another way food , in other words ingredients[i] May contain recipes Another string in .

And give you an array of strings supplies , It contains all the raw materials you had at the beginning , You have an unlimited number of raw materials .

Please return to all the dishes you can make . You can In any order Return to them .

Note that the two dishes may contain each other in their raw materials .

Example 1：

 Input ：recipes = ["bread"], ingredients = [["yeast","flour"]], supplies = ["yeast","flour","corn"]
 Output ：["bread"]
 explain ：
 We can make  "bread" , Because we have raw materials  "yeast"  and  "flour" .

Example 2：

 Input ：recipes = ["bread","sandwich"], ingredients = [["yeast","flour"],["bread","meat"]], supplies = ["yeast","flour","meat"]
 Output ：["bread","sandwich"]
 explain ：
 We can make  "bread" , Because we have raw materials  "yeast"  and  "flour" .
 We can make  "sandwich" , Because we have raw materials  "meat"  And can make raw materials  "bread" .

Example 3：

 Input ：recipes = ["bread","sandwich","burger"], ingredients = [["yeast","flour"],["bread","meat"],["sandwich","meat","bread"]], supplies = ["yeast","flour","meat"]
 Output ：["bread","sandwich","burger"]
 explain ：
 We can make  "bread" , Because we have raw materials  "yeast"  and  "flour" .
 We can make  "sandwich" , Because we have raw materials  "meat"  And can make raw materials  "bread" .
 We can make  "burger" , Because we have raw materials  "meat"  And can make raw materials  "bread"  and  "sandwich" .

Example 4：

 Input ：recipes = ["bread"], ingredients = [["yeast","flour"]], supplies = ["yeast"]
 Output ：[]
 explain ：
 We can't make any dishes , Because we only have raw materials  "yeast" .

Problem solving

Method 1 ： Violent simulation

Made from existing raw materials , Put the newly cooked dishes , Also added to raw materials , Repeat until no new dishes are added , Just return the result

class Solution {
    
public:
    vector<string> findAllRecipes(vector<string>& recipes, vector<vector<string>>& ingredients, vector<string>& supplies) {
    
        vector<string> res;
        unordered_set<string> set;
        for(string& s:supplies){
    // Record existing raw materials 
            set.insert(s);
        }

        int preLen;// The current length of all raw materials 
        while(true){
    
            int preLen=set.size();
            for(int i=0;i<recipes.size();i++){
    
                if(set.count(recipes[i])) continue;
                vector<string> tmp=ingredients[i];
                bool ok=true;// If true It means you can cook this dish 
                for(int j=0;j<tmp.size();j++){
    
                    if(!set.count(tmp[j])){
    
                        ok=false;
                        break;
                    }
                }
                if(ok){
    // If this dish can be made 
                    set.insert(recipes[i]);// This dish is added as raw material 
                    res.push_back(recipes[i]);// Save results 
                }
            }
            if(set.size()<=preLen) break;// If the raw materials are no longer increased , It means that the rest of the dishes can't be made 
        }
        return res;

    }
};

Method 2 ： A topological sort

Starting from raw materials , When the corresponding degree of the dish is 0 When , It indicates that the raw materials are complete , Add the dishes to the raw materials .
Get a penetration of 0 The point of , It's a dish that can be made .

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> indeg;
        int n=recipes.size();
        for(int i=0;i<n;i++){
    
            for(int j=0;j<ingredients[i].size();j++){
    
                graph[ingredients[i][j]].push_back(recipes[i]);
                indeg[recipes[i]]++;
            }
        }
        queue<string> q;
        for(string& s:supplies){
    
            q.push(s);
        }

        vector<string> res;
        while(!q.empty()){
    
            string x=q.front();
            q.pop();
            for(string& y:graph[x]){
    
                if(--indeg[y]==0){
    
                    q.push(y);
                    res.push_back(y);
                }
            }
            
        }
        return res;
    }
};