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