Почему это работает
- У рецепта счётчик дойдёт до 0, только когда каждый его ингредиент выйдет из очереди, а в очередь попадают только припасы и приготовленные рецепты.
- Приготовленный рецепт идёт в очередь как припас, поэтому до рецепта, которому он нужен, тоже дойдёт очередь — как до пасты после теста.
- Ингредиент, которого нет в припасах и который нельзя приготовить, из очереди не выйдет никогда, поэтому у рецепта с ним — и у всех рецептов после него — счётчик остаётся больше 0. Так же выше 0 остаются рецепты, которые нужны друг другу по кругу.
Сложность
Время O(r + i + s) для r рецептов, i ингредиентов во всех списках и s припасов: каждая запись в списках становится одной стрелкой, по ней проходим один раз, и каждый предмет попадает в очередь не больше одного раза. Память O(r + i + s) на стрелки, счётчики и очередь.
дальшеТеперь реши её сам, без подсказок.
Решить на LeetCode ↗