本文涉及知识点
有向图的拓扑排序 C++图论
LeetCode2115. 从给定原材料中找到所有可以做出的菜
你有 n 道不同菜的信息。给你一个字符串数组 recipes 和一个二维字符串数组 ingredients 。第 i 道菜的名字为 recipes[i] ，如果你有它 所有 的原材料 ingredients[i] ，那么你可以 做出 这道菜。一道菜的原材料可能是 另一道 菜，也就是说 ingredients[i] 可能包含 recipes 中另一个字符串。
同时给你一个字符串数组 supplies ，它包含你初始时拥有的所有原材料，每一种原材料你都有无限多。
请你返回你可以做出的所有菜。你可以以 任意顺序 返回它们。
注意两道菜在它们的原材料中可能互相包含。
示例 1：
输入：recipes = [“bread”], ingredients = [[“yeast”,“flour”]], supplies = [“yeast”,“flour”,“corn”]
输出：[“bread”]
解释：
我们可以做出 “bread” ，因为我们有原材料 “yeast” 和 “flour” 。
示例 2：
输入：recipes = [“bread”,“sandwich”], ingredients = [[“yeast”,“flour”],[“bread”,“meat”]], supplies = [“yeast”,“flour”,“meat”]
输出：[“bread”,“sandwich”]
解释：
我们可以做出 “bread” ，因为我们有原材料 “yeast” 和 “flour” 。
我们可以做出 “sandwich” ，因为我们有原材料 “meat” 且可以做出原材料 “bread” 。
示例 3：
输入：recipes = [“bread”,“sandwich”,“burger”], ingredients = [[“yeast”,“flour”],[“bread”,“meat”],[“sandwich”,“meat”,“bread”]], supplies = [“yeast”,“flour”,“meat”]
输出：[“bread”,“sandwich”,“burger”]
解释：
我们可以做出 “bread” ，因为我们有原材料 “yeast” 和 “flour” 。
我们可以做出 “sandwich” ，因为我们有原材料 “meat” 且可以做出原材料 “bread” 。
我们可以做出 “burger” ，因为我们有原材料 “meat” 且可以做出原材料 “bread” 和 “sandwich” 。
示例 4：
输入：recipes = [“bread”], ingredients = [[“yeast”,“flour”]], supplies = [“yeast”]
输出：[]
解释：
我们没法做出任何菜，因为我们只有原材料 “yeast” 。
提示：
n == recipes.length == ingredients.length
1 <= n <= 100
1 <= ingredients[i].length, supplies.length <= 100
1 <= recipes[i].length, ingredients[i][j].length, supplies[k].length <= 10
recipes[i], ingredients[i][j] 和 supplies[k] 只包含小写英文字母。
所有 recipes 和 supplies 中的值互不相同。
ingredients[i] 中的字符串互不相同。
拓扑排序
如果初始拥有所有原理 ⟺ \iff ⟺ 所有出度为0的节点，都可以消除。可以用拓扑排序。
初始没有的材料（没有出现在配方或供应中)，我们让其自环，这样不会被TopSort消除。且统一为节点n。
代码
核心代码
class CTopSort
{
public:
template <class T = vector<int> >
void Init(const vector<T>& vNeiBo,bool bDirect )
{
const int iDelOutDeg = bDirect ? 0 : 1;
m_c = vNeiBo.size();
m_vBackNeiBo.resize(m_c);
vector<int> vOutDeg(m_c);
for (int cur = 0; cur < m_c; cur++)
{
vOutDeg[cur] = vNeiBo[cur].size();
for (const auto& next : vNeiBo[cur])
{
m_vBackNeiBo[next].emplace_back(cur);
}
}
vector<bool> m_vHasDo(m_c);
queue<int> que;
for (int i = 0; i < m_c; i++)
{
if ( vOutDeg[i] <= iDelOutDeg)
{
m_vHasDo[i] = true;
if (OnDo(i)) {
que.emplace(i);
}
}
}
while (que.size())
{
const int cur = que.front();
que.pop();
for (const auto& next : m_vBackNeiBo[cur])
{
if (m_vHasDo[next] )
{
continue;
}
vOutDeg[next]--;
if (vOutDeg[next] <= iDelOutDeg )
{
m_vHasDo[next] = true;
if (OnDo(next)) {
que.emplace(next);
}
}
}
};
}
int m_c;
protected:
virtual bool OnDo( int cur) = 0;
vector<vector<int>> m_vBackNeiBo;
};
class CMyTopSort :public CTopSort
{
public:
CMyTopSort(vector<string>& recipes):m_recipes(recipes){
}
virtual bool OnDo(int cur) override
{
if (cur < m_recipes.size() ) m_ans.emplace_back(m_recipes[cur]);
return true;
}
vector<string>& m_recipes;
vector<string> m_ans;
};
class Solution {
public:
vector<string> findAllRecipes(vector<string>& recipes, vector<vector<string>>& ingredients, vector<string>& supplies) {
unordered_map<string, int> mCode;
for (const auto& s : recipes) {
if (mCode.count(s))continue;
mCode[s] = mCode.size();
}
for (const auto& s : supplies) {
if (mCode.count(s))continue;
mCode[s] = mCode.size();
}
const int N = mCode.size();
vector<vector<int>> neiBo(N+1);
neiBo.back().emplace_back(N);
for (int i = 0; i < ingredients.size(); i++) {
for (const auto& s : ingredients[i]) {
if (mCode.count(s))
{
neiBo[i].emplace_back(mCode[s]);
}
else {
neiBo[i].emplace_back(N);
}
}
}
CMyTopSort topSort(recipes);
topSort.Init(neiBo, true);
return topSort.m_ans;
}
};
单元测试
vector<vector<string>> ingredients;
vector<string> recipes, supplies;
TEST_METHOD(TestMethod11)
{
recipes = { "bread" }, ingredients = { {"yeast","flour"} }, supplies = { "yeast","flour","corn" };
auto res = Solution().findAllRecipes(recipes, ingredients, supplies);
AssertEx({ "bread" }, res);
}
TEST_METHOD(TestMethod12)
{
recipes = { "bread","sandwich" }, ingredients = { {"yeast","flour"},{"bread","meat"} }, supplies = { "yeast","flour","meat" };
auto res = Solution().findAllRecipes(recipes, ingredients, supplies);
AssertEx( {"bread","sandwich" }, res);
}
TEST_METHOD(TestMethod13)
{
recipes = { "bread","sandwich","burger" }, ingredients = { {"yeast","flour"},{"bread","meat"},{"sandwich","meat","bread"} }, supplies = { "yeast","flour","meat" };
auto res = Solution().findAllRecipes(recipes, ingredients, supplies);
AssertEx({ "bread","sandwich","burger" }, res);
}
TEST_METHOD(TestMethod14)
{
recipes = { "bread" }, ingredients = { {"yeast","flour"} }, supplies = { "yeast" };
auto res = Solution().findAllRecipes(recipes, ingredients, supplies);
AssertEx({ }, res);
}
TEST_METHOD(TestMethod15)
{
recipes = { "fe","nvvj","kps","ik","gd","gjpz","cff","ljb","ybxsh","vtu","htsn","jwwxz","znoem","h","mlg","ggd","bkinz","pzjna","pxum" },
ingredients = { {"zqg"},{"zqg"},{"t"},{"zqg"},{"bkinz","ggd","ljb","ybxsh","nvvj","pzjna","cff"},{"kps","nvvj","pxum","ik","cff","ybxsh","h"},{"yyym"},{"zqg"},{"htsn","vtu"},{"kfukc"},{"zqg"},{"zqg"},{"a"},{"zqg","gd","ybxsh","ggd","ljb"},{"ybxsh","pxum","h","bkinz"},{"zqg"},{"zqg"},{"mu"},{"zqg"} },
supplies = { "zqg" };
auto res = Solution().findAllRecipes(recipes, ingredients, supplies);
AssertEx({ "fe","nvvj","ik","ljb","htsn","jwwxz","ggd","bkinz","pxum" }, res);
}
