Где применяется
1. Задача
У тебя есть граф и один вопрос к нему: есть ли путь, который выходит из узла, проходит через другие узлы и возвращается туда, откуда вышел? Такое кольцо называют циклом (cycle). В карте дорог, где можно проехать по кругу, цикл есть. В генеалогическом древе его нет.
Ты уже умеешь обходить граф: в ширину с очередью (шаг 88) и в глубину, когда идёшь по одному пути до конца и потом возвращаешься (шаг 89). Обход сразу отвечает на вопрос про цикл. Если во время обхода ты пришёл в узел, где уже был, ты, возможно, нашёл кольцо.
Сложность в слове «возможно». Точное правило разное для двух видов графа, и неверное правило находит циклы там, где их нет. В этом уроке разберём оба правила.
Этот шаг из платной части
Бесплатные шаги в начале курса (их 33) открыты всем: урок, задача и тесты. Этот шаг открывается с полным доступом. Начни с бесплатного аккаунта и бесплатных шагов.
Завести бесплатный аккаунтПосмотреть, что входитНа LeetCode
Задачи, где нужно узнать, есть ли в графе петля, например зависимости, которые ждут друг друга. В ориентированном графе цикл замыкает сосед, который ещё в стеке поиска в глубину, а в неориентированном любой посещённый сосед, кроме родителя.
Пререквизиты это ориентированные рёбра, и курсы можно пройти ровно тогда, когда проверка из урока не находит цикла.
Клетки с одной буквой образуют неориентированный граф, и ответ решает проверка родителя из подложенной ошибки.
Запусти проверку для ориентированного графа с тремя состояниями, и узел безопасен, если его обход закончился, не встретив узла, который ещё в стеке.
У каждого узла не больше одного исходящего ребра, так что иди от каждого непосещённого узла, запоминай шаг, на котором увидел узел, и повтор на текущем пути даст длину цикла.