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