Алгоритм Косарайю: два обхода и все компоненты

Если ты помнишь все три шага Косарайю, понимаешь роль порядка выхода и умеешь объяснить, почему обход по развёрнутому графу не вылезает за пределы компоненты, листай до «Теперь сам».

Как думаешь, чем плох наивный способ

Простейший способ найти компоненты: для каждой вершины запустить обход по графу (кто достижим из неё) и обход по развёрнутому графу (кто достигает её), а потом пересечь множества. Прежде чем читать дальше, посчитай цену такого способа для V = 10⁵ и E = 10⁶ - и сравни с O(V + E).

На что это похоже

Разбор запутанного клубка ниток. Если дёргать за случайную нитку, вытянешь кусок вместе с соседними петлями - границы клубка не видно. Но если начать с той нитки, которая заведомо лежит СВЕРХУ, она снимается целиком и одна. Весь фокус Косарайю - найти такую «верхнюю» нитку, и время выхода из обхода как раз её показывает.

Механизм: три шага

# 1) первый обход: копим порядок ВЫХОДА
order = []
visited = [False] * V
def dfs1(v):
    visited[v] = True
    for u in adj[v]:
        if not visited[u]:
            dfs1(u)
    order.append(v)                 # записали при выходе

for v in range(V):
    if not visited[v]:
        dfs1(v)

# 2) разворачиваем граф: каждое ребро u → v становится v → u
radj = [[] for _ in range(V)]
for u in range(V):
    for v in adj[u]:
        radj[v].append(u)

# 3) второй обход по РАЗВЁРНУТОМУ графу в порядке УБЫВАНИЯ времени выхода
comp = [-1] * V
def dfs2(v, c):
    comp[v] = c
    for u in radj[v]:
        if comp[u] == -1:
            dfs2(u, c)

c = 0
for v in reversed(order):           # от последнего вышедшего к первому
    if comp[v] == -1:
        dfs2(v, c)
        c += 1                      # каждое дерево второго обхода - компонента

Цена: два обхода по O(V + E) плюс построение развёрнутого графа O(V + E). Памяти нужно вдвое больше - хранится и граф, и его разворот.

Есть и одноходовый алгоритм - Тарьяна: он находит компоненты за один обход, без разворота графа, с помощью стека и величины «минимальное время входа, достижимое из поддерева». Асимптотика та же O(V + E), констант меньше, память меньше - но рассуждение тоньше. Косарайю берут, когда важна понятность; Тарьяна - когда важна экономия.

Правило

Косарайю: (1) обход по графу, вершины копятся в порядке ВЫХОДА; (2) разворот графа; (3) обход по развёрнутому графу в порядке УБЫВАНИЯ времени выхода - каждое дерево второго обхода есть компонента сильной связности. Цена O(V + E) и двойная память. Порядок во втором проходе обязателен: он гарантирует, что обход стартует в компоненте, из которой в развёрнутом графе нельзя выйти.

Разбор: прогоняем на графе

Граф: a→b, b→c, c→a, c→d, d→e, e→d, d→f. Компоненты мы уже знаем из прошлого урока: {a,b,c}, {d,e}, {f}.

Шаг 1. Стартуем с a. Вход a → вход b → вход c → ребро c→a: серая, не идём → ребро c→d → вход d → вход e → ребро e→d: серая, не идём → выход e → ребро d→f → вход f (рёбер нет) → выход f → выход d → выход c → выход b → выход a. Порядок выхода: order = [e, f, d, c, b, a].

Шаг 2. Разворачиваем: b→a, c→b, a→c, d→c, e→d, d→e, f→d.

Шаг 3. Идём с конца order, то есть a, b, c, d, f, e. - a не раскрашена → обход по развёрнутому графу: a → c → b (из b ведёт b→a, но a уже в компоненте; из c ведёт c→b). Собрали компоненту 0: {a, b, c}. Наружу выйти не удалось - рёбра c→d в развёрнутом графе нет, есть d→c, а оно ведёт внутрь. - b, c уже раскрашены - пропускаем. - d не раскрашена → обход: d → e (ребро d→e в развёрнутом графе есть), из e ведёт e→d - уже наша. Ребро d→c ведёт в компоненту 0, но c уже раскрашена. Компонента 1: {d, e}. - f не раскрашена → обход: из f ведёт f→d, но d раскрашена. Компонента 2: {f}.

Три компоненты - совпало с ручным разбором. Заметь, где сработал порядок: мы начали с a, вершины с максимальным временем выхода, и именно её компонента в развёрнутом графе оказалась «глухой».

Разбор: почему это работает

Ключевая лемма: вершина с наибольшим временем выхода лежит в компоненте, которая в конденсации является ИСТОКОМ (в неё не ведёт ни одно ребро извне).

Почему: пусть компонента C не исток, то есть есть ребро из компоненты D в C. Покажем, что у какой-нибудь вершины D время выхода больше, чем у любой вершины C. Возможны два случая.

Если обход вошёл в D раньше, чем в любую вершину C, то пока D серая, он доберётся по этому ребру до C и обойдёт её целиком (компонента сильно связна, из любой её вершины достижимы все остальные), а вложенные вызовы завершатся раньше объемлющего - значит вся C выйдет до выхода из D. Если же обход вошёл в какую-то вершину C раньше, чем в D, то он снова обойдёт всю C и закончит её ДО того, как войдёт в D: вернуться из C в D нельзя (иначе они были бы одной компонентой), поэтому никакая вершина C не может оставаться серой, когда обход входит в D. В обоих случаях максимум времени выхода находится не в C, а выше по конденсации. Значит вершина с глобальным максимумом лежит в компоненте-истоке.

Теперь разворот. После него все рёбра конденсации меняют направление, и исток становится СТОКОМ: из него нет рёбер наружу. Запуская обход по развёрнутому графу из вершины с максимальным временем выхода, мы стартуем внутри компоненты-стока - и обход физически не может выйти за её пределы, а внутри достигает всех её вершин (компонента сильно связна, и разворот сильную связность сохраняет). Значит первое дерево - ровно одна компонента.

Дальше по индукции: раскрашенные вершины выбрасываются, и следующая нераскрашенная вершина с наибольшим временем выхода снова оказывается в истоке ОСТАВШЕЙСЯ конденсации. Уточнение, без которого индукция не держится: у второй и следующих компонент рёбра наружу в развёрнутом графе уже есть - ведут они в компоненты, найденные раньше. Обход туда не уходит не потому, что рёбер нет, а потому, что те вершины уже раскрашены и пропускаются. Каждое дерево второго обхода - ровно одна компонента, и все они найдены за два прохода.

Что ломается без этого

Первое: запустить второй обход по ИСХОДНОМУ графу, а не по развёрнутому - тогда обход из истока уйдёт вниз по конденсации и склеит в одну компоненту всё, что из истока достижимо. Второе: взять во втором проходе порядок возрастания времени выхода (или порядок номеров) - обход начнётся не в истоке, выйдет за пределы компоненты и снова всё склеит. Третье: пересчитать порядок выхода на развёрнутом графе - нужен порядок из ПЕРВОГО прохода. Четвёртое: забыть внешний цикл в первом проходе - вершины, недостижимые из стартовой, не попадут в order, и их компоненты потеряются. Пятое, практическое: строить разворот графа заново на каждом запросе - если компонент ищут часто, разворот стоит построить один раз и хранить, либо взять алгоритм Тарьяна, которому разворот не нужен вовсе.

Зачем это в работе

Компоненты сильной связности - это «группы взаимозависимого», и находить их нужно всюду, где есть направленные связи. Сборка и пакеты: модули одной компоненты придётся собирать вместе, и система скажет это пользователю вместо абстрактного «цикл». Компиляторы: взаимно рекурсивные функции образуют компоненту в графе вызовов - их анализируют и оптимизируют совместно. Статический анализ и рефакторинг: компоненты в графе зависимостей классов показывают клубки, которые надо развязывать. 2-SAT: ответ читается прямо из компонент графа импликаций - если переменная и её отрицание попали в одну компоненту, решения нет. Анализ графа ссылок, поиск сообществ, обнаружение взаимных блокировок, проверка достижимости в огромных графах (сначала конденсация, потом ДАГ, на котором всё считается быстро) - везде один и тот же алгоритм из двух обходов.

Теперь сам

Граф: 1→2, 2→1, 2→3, 3→4, 4→3. Первый обход стартует с вершины 1, соседи по возрастанию. Выпиши порядок выхода, разверни граф и проведи второй обход. Сколько получится компонент?