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