MediumRating 1679
2115. Find All Possible Recipes from Given Supplies
arrayhash-tablestringgraphtopological-sort
解題說明
Find All Possible Recipes from Given Supplies
題目描述： 給定一些食譜 recipes，每個食譜需要一組材料 ingredients[i]。有一組基本供給品 supplies。食譜也可以作為其他食譜的材料。求所有能做出來的食譜。
解題思路： 這是一個依賴關係的拓撲排序問題。
- 將每個食譜視為圖中的一個節點。
- 若食譜 A 需要食譜 B 作為材料，則有一條從 B 到 A 的邊。
- 基本供給品視為已經就緒的節點。
- 使用拓撲排序（Kahn's algorithm）：
- 對每個食譜，統計尚未滿足的材料數量（入度）。
- 基本供給品能直接減少依賴它們的食譜的入度。
- 入度為 0 的食譜可以製作，加入佇列。
- 製作出的食譜可以作為其他食譜的材料，繼續減少入度。
- 所有入度歸 0 的食譜即為答案。
C++ 解法
複雜度分析
時間複雜度：O(R * I + S) — R 為食譜數量，I 為平均材料數量，S 為供給品數量。建圖和拓撲排序各遍歷一次所有邊。
空間複雜度：O(R * I + S) — 依賴圖、入度陣列和供給品集合。
虛擬碼
1. Put all supplies into an available set. 2. For each recipe i, count unsatisfied ingredients (not in available set) as indegree[i]. 3. Build reverse dependency map: ingredient → list of recipe indices that need it. 4. Enqueue all recipes with indegree 0. 5. BFS: a. Dequeue recipe idx, add to result. b. For each recipe that depends on recipes[idx]: decrement indegree, enqueue if 0. 6. Return result.
其他解法
-
DFS + 記憶化：對每個食譜做 DFS 檢查是否所有材料都能取得（基本供給品或可做出的食譜）。用記憶化避免重複檢查。需要處理迴圈依賴（標記為不可做）。時間複雜度 O(R * I)。
-
反覆掃描法：反覆遍歷所有食譜，每次將可做出的加入 available 集合。重複直到沒有新食譜被加入。最壞情況 O(R^2 * I)，但實作簡單。
延伸思考
- 若材料有數量限制（每種只有有限個），如何修改演算法？
- 若食譜有優先順序（優先做高價值的），如何調整拓撲排序？
- 若存在迴圈依賴（A 需要 B，B 需要 A），如何偵測並報告哪些食譜因迴圈而無法製作？