从给定原材料中找到所有可以做出的菜

记住「原料指向菜、need 记缺料数、归零即做出入队」,下面逐帧套它。

先把初始原料 yeast、flour、meat 标为起点(绿),它们一开始就备齐。接下来逐道菜建图:让每样原料连一条边指向「用到它的菜」,并记下每道菜的 need(需要几样原料)。

菜「bread」需要 yeast、flour 共 2 样:这几样各连一条边指向 bread,并设 need[bread] = 2(它的入度)。

菜「sandwich」需要 bread、meat 共 2 样:这几样各连一条边指向 sandwich,并设 need[sandwich] = 2(它的入度)。

菜「burger」需要 sandwich、meat、bread 共 3 样:这几样各连一条边指向 burger,并设 need[burger] = 3(它的入度)。

把三样初始原料 yeast、flour、meat 全部入队。右侧面板记着每道菜当前还缺几样:bread 缺 2、sandwich 缺 2、burger 缺 3。开始按队列逐个处理。

弹出已备齐的「yeast」。看依赖它的菜:bread。逐个把它们的 need 减 1。

「yeast」是「bread」的原料之一:need[bread] 减 1,现在还缺 1 样,先放着,等其余原料备齐。

弹出已备齐的「flour」。看依赖它的菜:bread。逐个把它们的 need 减 1。

「flour」是「bread」的原料之一:need[bread] 减到 0,原料全凑齐!做出「bread」,计入答案并入队(它接下来又能当别人的原料)。

弹出已备齐的「meat」。看依赖它的菜:sandwich、burger。逐个把它们的 need 减 1。

「meat」是「sandwich」的原料之一:need[sandwich] 减 1,现在还缺 1 样,先放着,等其余原料备齐。

「meat」是「burger」的原料之一:need[burger] 减 1,现在还缺 2 样,先放着,等其余原料备齐。

弹出已备齐的「bread」。看依赖它的菜:sandwich、burger。逐个把它们的 need 减 1。

「bread」是「sandwich」的原料之一:need[sandwich] 减到 0,原料全凑齐!做出「sandwich」,计入答案并入队(它接下来又能当别人的原料)。

「bread」是「burger」的原料之一:need[burger] 减 1,现在还缺 1 样,先放着,等其余原料备齐。

弹出已备齐的「sandwich」。看依赖它的菜:burger。逐个把它们的 need 减 1。

「sandwich」是「burger」的原料之一:need[burger] 减到 0,原料全凑齐!做出「burger」,计入答案并入队(它接下来又能当别人的原料)。

弹出已备齐的「burger」。没有哪道菜直接以它为原料(或依赖它的菜已处理),它不再解锁新东西,继续看下一个。

队列清空。一路连锁:yeast+flour 解锁 bread → bread+meat 解锁 sandwich → sandwich+meat+bread 解锁 burger。答案 = [bread, sandwich, burger],三道菜全部可做。

回看核心:拓扑排序按「原料就绪顺序」一层层推进,每道菜恰在它最后一样原料备齐的那一刻 need 归零、被做出。没有初始原料能打破的环(循环依赖)永远 need 不归零,自然落选。

边界:够料即做;循环依赖全落选;缺料卡住者落选。

两个延伸:循环依赖自动落选;DFS 记忆化等价但要防环。