Paste: DFS

Author: aa
Mode: c++
Date: Thu, 12 May 2022 05:38:22
Plain Text |
class Solution {
        
private:
        unordered_map<string,vector<string>> rec_ing;
        //建set
        unordered_set<string> supplies_set;
       

public:
    vector<string> findAllRecipes(vector<string>& recipes, vector<vector<string>>& ingredients, vector<string>& supplies) {

        for(auto sup:supplies)
        {
            supplies_set.emplace(sup);
        }

        for(int i=0;i<ingredients.size();i++)
        {
            rec_ing[recipes[i]]=ingredients[i];
        }

        vector<string> ans;

        for(int i=0;i<recipes.size();i++)
        {   
            string rec=recipes[i];
            unordered_set<string> visted;
            visted.emplace(rec);//check
            if(dfs(rec,visted))
                ans.emplace_back(rec);
        }

        return ans;
    }


    bool dfs(string rec,unordered_set<string>& visited)
    {
        if(supplies_set.find(rec)!=supplies_set.end())
        return true;        

        if(rec_ing.find(rec) == rec_ing.end()&&(supplies_set.find(rec)==supplies_set.end()))//supplies no recipes no
        {
            return false;
        }
        bool res=true;
        for(auto ingr:rec_ing[rec])
        {
            if((visited.find(ingr)==visited.end())&&supplies_set.find(ingr)==supplies_set.end())//not visited[ingr] and ingr not in supplies
            {
                visited.emplace(ingr);
                res=res&&dfs(ingr,visited);
                visited.erase(ingr);
            }
            else if((visited.find(ingr)!=visited.end())&&(supplies_set.find(ingr)==supplies_set.end()))
            {
                return false;
            }
        }
        return res;
    }
};

New Annotation

Summary:
Author:
Mode:
Body: