网站开发技术 下载php整站最新版本下载

拓扑排序

题面

题目链接：2115. 从给定原材料中找到所有可以做出的菜 - 力扣（LeetCode）

你有 n 道不同菜的信息。给你一个字符串数组 recipes 和一个二维字符串数组 ingredients 。第 i 道菜的名字为 recipes[i] ，如果你有它 所有 的原材料 ingredients[i] ，那么你可以 做出 这道菜。一道菜的原材料可能是 另一道 菜，也就是说 ingredients[i] 可能包含 recipes 中另一个字符串。

同时给你一个字符串数组 supplies ，它包含你初始时拥有的所有原材料，每一种原材料你都有无限多。

请你返回你可以做出的所有菜。你可以以 任意顺序 返回它们。

注意两道菜在它们的原材料中可能互相包含。

解题思路

做出一个菜，可以由这个菜作为原料做出另一个，且原料无限

很容易幻想出一个有向图，从原料指向各个目标菜，而拥有公共原料，且之间存在互相作为原料的情况则可以看作图的后序

了解过或者学习过拓扑排序的，到这里应该就能判断谁作为队列的初始元素了

但是题目给出的是原料有哪些，需要做的菜有哪些，它们又各自需要哪些作为原料

所以我们需要用哈希表存储这些关系，避免大量重复的遍历寻找

哈希表1：一个原料能做出哪些菜

哈希表2：一个菜的入度为几（因为每个元素都为string类型，所以也是需要用哈希表）

拓扑排序套路写法

class Solution {
public:vector<string> findAllRecipes(vector<string>& recipes,vector<vector<string>>& ingredients,vector<string>& supplies) {unordered_map<string, int> indegree;unordered_map<string, vector<string>> out;queue<string> q;vector<string> ans;for (string i : supplies)q.push(i);for (int i = 0; i < recipes.size(); i++) {indegree[recipes[i]] = ingredients[i].size();for(string var:ingredients[i]){out[var].push_back(recipes[i]);}}while (!q.empty()) {string now = q.front();q.pop();for(string aim:out[now]){if(--indegree[aim]==0){ans.push_back(aim);q.push(aim);}}}return ans;}
};