Где применяется
1. Задача
Раньше ты считал связные группы в неориентированном графе (шаг 91). Там связность была простой: если между двумя людьми есть путь, они в одной группе. Путь работает в обе стороны, потому что дружба взаимна.
Теперь у рёбер есть направление. Если узел 0 указывает на узел 1, это ещё не значит, что 1 указывает обратно на 0. Так устроены улицы с односторонним движением. Два перекрёстка попадают в одну группу, только если от первого можно проехать ко второму И от второго обратно к первому, соблюдая направления всех улиц.
Такая группа называется компонентой сильной связности (strongly connected component, SCC). Это самая большая группа узлов, где из каждого узла можно дойти до каждого другого, двигаясь по направлениям рёбер. Задача: дан ориентированный граф, посчитать, сколько в нём SCC.
Граф совсем без циклов распадается на n компонент, по одной на узел: вперёд пройти можно, а вернуться нельзя никогда. Один ориентированный цикл через все узлы это одна компонента: по нему можно объехать всё. Большинство графов лежат где-то между этими крайними случаями.
Этот шаг из платной части
Бесплатные шаги в начале курса (их 33) открыты всем: урок, задача и тесты. Этот шаг открывается с полным доступом. Начни с бесплатного аккаунта и бесплатных шагов.
Завести бесплатный аккаунтПосмотреть, что входитНа LeetCode
Задачи на ориентированный граф про циклы и взаимную достижимость, например самый длинный цикл или сколько вершин можно обойти из каждого старта. LeetCode редко называет компоненты сильной связности по имени, а два прохода DFS, по графу и по перевёрнутому графу, находят их за O(V + E).
У каждой вершины не больше одного исходящего ребра, поэтому компонента больше чем из одной вершины это ровно один цикл, и ответ это самая большая из них.
Пометь вершины в компонентах из 2 и более вершин или с ребром в себя. Каждая вершина, из которой можно дойти до помеченной, тоже небезопасна.
У каждой вершины ровно одно исходящее ребро, поэтому вершина на цикле обходит ровно длину цикла, а любая другая на одну вершину больше, чем та, куда она указывает.