# Paste: DFS

Author: aa c++ Thu, 12 May 2022 05:44:19
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: textPostgreSQLPowerCenter Parameter Fileactionscriptadaada95ans-forth94antantlrantlr4apacheconfapdlapplescriptaspaspect-jassembly-agcassembly-agsassembly-arm32assembly-m68kassembly-macro32assembly-mcs51assembly-parrotassembly-r2000assembly-x86avroawkbbatchbbjbcelbeanshellbibtexbinsource-agccc#c++cfscriptchillcilclipsclojurecmakecobolcoffeescriptcoldfusioncplex-lpcsscsvcvs-commitddartdjangodockerfiledotdoxygendrawj2ddsssleiffelembperlerlangfactorfhtmlforthfortranfortran90foxprofreemarkergcbasicgettextgherkingnuplotgogradlegroovygsphaskellhaxehexhl7v2hlslhtaccesshtmlhxmli4glicalendariconidlinforminiinno-setupinterlisiojamonjavajava module-infojavaccjavafxjavascriptjcljedit-actionsjflexjhtmljmkjsonjspkotlinlatexlexlilypondlispliterate-haskelllogslogtalklotosluam4macroschedulermailmakefilemaplemarkdownmavenmavscriptmetapostmlmodula3moinmqscmustache-templatemxmlmyghtymysqln3netrexxnqcnsis2objective-cobjectrexxoccamomnimarkopensipsoutlinepascalpatchperlphppikepl-sqlpl-sql9pl1plaintexplantumlpop11postscriptpovraypowerdynamopowershellprogressprologpropertiesprotobufpspptlpurepvwavepyrexpythonqdocrakefilercprdrebolredcoderelax-ng-compactrenderman-ribrestrfcrhtmlroffrpm-specrtfrubyrustrviews#s+sassbtscalaschemesdl/prsgmlshellscriptshtmlsipsippslateslaxsmalltalksmartysmi-mibsparqlsql-loadersqrsquidconfstatasvn-commitswiftswigtcltemplate-toolkittextexinfotldtransact-sqltsptwikityposcripturluscriptvalavbscriptvelocityverilogvhdlvisualbasicvrml2wellknowntextxmlxqxslyabyamlzpt