Find Eventual Safe States

Средняя№802от тупиков назад

Дан ориентированный граф: для каждой вершины — список вершин, в которые из неё идут стрелки. Вершина без исходящих стрелок — тупик. Вершина безопасна, если любой путь из неё, по каким бы стрелкам он ни шёл, заканчивается в тупике. Нужно вернуть все безопасные вершины по возрастанию. Наш пример: 0 → [1, 3], 1 → [2, 5], 2 → [], 3 → [4], 4 → [6], 5 → [], 6 → [3, 5]. Ответ — [1, 2, 5].

802 Find Eventual Safe StatesРазбор · 1×

Пример: 7 вершин. Число над вершиной — её исходящая степень: выходы, про которые ещё неизвестно, что они безопасны. Прогон идёт по стрелкам назад, от тупиков.

0123456очередьначало слева—безопасны—
есть непроверенные выходыв очередитекущая вершинакуда ведёт развёрнутая стрелкабезопаснанебезопасна: путь из неё может зациклиться

Разворачиваем стрелки, чтобы знать, кто ведёт в каждую вершину: 1 ← 0; 2 ← 1; 3 ← 0, 6; 4 ← 3; 5 ← 1, 6; 6 ← 4

01/25
сначала · назад · пуск · шаг
Скорость
1function eventualSafeNodes(graph):
2 back = every arrow of graph reversed
3 outdegree = arrows out of each node
4 queue = nodes with outdegree 0
5 safe = []
6 while queue is not empty:
7 node = queue.popFront()
8 safe.pushBack(node)
9 for prev in back[node]:
10 decrease outdegree[prev] by 1
11 if outdegree[prev] is 0:
12 queue.pushBack(prev)
13 return sorted(safe)
состояние
outdegree
–
queue
–
safe
–
node
–
prev
–
историянажмите шаг, чтобы вернуться

← → шаг · пробел — пауза

Почему это работает

  1. Тупик безопасен. Вершина безопасна ровно тогда, когда все её стрелки ведут в безопасные вершины, поэтому она попадает в очередь, как только число непроверенных выходов станет 0.
  2. У вершины в цикле всегда остаётся стрелка, которая идёт дальше по кругу, как и у вершины, из которой есть стрелка в цикл: их счётчик никогда не станет 0.
  3. Карточка считает входящие стрелки и начинает с того, что ничего не ждёт; здесь стрелки проходятся назад, поэтому считаем исходящие, а начинаем с тупиков.

Сложность

Время O(n + e + n log n) для n вершин и e стрелок: каждую стрелку разворачиваем и проходим назад один раз, каждая вершина попадает в очередь не больше одного раза, а в конце безопасные вершины сортируются. Память O(n + e) на развёрнутые стрелки, счётчики и очередь.

дальшеТеперь реши её сам, без подсказок.

Решить на LeetCode ↗

Задача и её условие принадлежат LeetCode. Здесь — наш пересказ, наш пример и наше решение. Patterns Hero не связан с LeetCode.