Времена входа и выхода: обход, который оставляет следы

Если ты знаешь теорему о скобках, умеешь проверять «предок ли» двумя сравнениями и понимаешь, что серая вершина - это вершина на текущем пути, листай до «Теперь сам».

Как думаешь, что можно узнать потом

Обход прошёл по графу и закончился. Прежде чем читать дальше, подумай: какую информацию стоило бы запомнить по дороге, чтобы потом отвечать на вопросы вроде «лежит ли вершина v в поддереве вершины u» или «есть ли в графе цикл», не запуская обход заново? Подсказка: обход по своей природе - это вложенные вызовы, а вложенность легко описать двумя числами.

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

Журнал охранника, который ходит по зданию и отмечает: «22:00 вошёл в комнату A», «22:03 вошёл в B», «22:05 вышел из B», «22:07 вышел из A». По такому журналу видно, что B осматривали ВНУТРИ осмотра A - то есть B вложена в A по времени. И невозможна запись «вошёл в A, вошёл в B, вышел из A, вышел из B»: нельзя выйти из комнаты, не выйдя сначала из той, куда зашёл изнутри неё. Скобки либо вложены, либо стоят рядом.

Механизм: счётчик и три цвета

timer = 0
tin = [0] * V
tout = [0] * V
color = ['white'] * V          # white - не посещена, gray - вошли, black - вышли

def dfs(v):
    global timer
    color[v] = 'gray'
    tin[v] = timer; timer += 1
    for u in adj[v]:
        if color[u] == 'white':
            dfs(u)
    color[v] = 'black'
    tout[v] = timer; timer += 1

Счётчик ОДИН на весь обход и растёт и на входе, и на выходе - значит к концу он равен 2V, а все 2V меток различны. Цвета - это тот же массив visited, но с разделением на «вошли» и «вышли»:

белая  - ещё не трогали
СЕРАЯ  - вошли, но не вышли: вершина ЛЕЖИТ НА ТЕКУЩЕМ ПУТИ (на стеке рекурсии)
чёрная - обход её поддерева полностью закончен

Серый цвет - самая ценная часть. Он отвечает на вопрос «эта вершина сейчас у меня под ногами, на пути от старта сюда?», а из этого в следующем уроке получится поиск циклов.

Правило

Обход ведёт счётчик и записывает tin[v] при входе и tout[v] при выходе (счётчик растёт в обоих случаях, всего 2V различных меток). Теорема о скобках: для любых двух вершин отрезки [tin, tout] либо вложены, либо не пересекаются. Следствие: u - предок v в дереве обхода тогда и только тогда, когда tin[u] < tin[v] и tout[v] < tout[u], то есть проверка предка - O(1) после обхода. Цвета: белая - не посещена, СЕРАЯ - на текущем пути (вошли, не вышли), чёрная - закончена.

Разбор: считаем времена на графе

Граф ориентированный: a→b, a→d, b→c, c→d. Обход стартует из a, соседи перебираются в порядке записи.

timer=0  вход a   tin[a]=0
timer=1  вход b   tin[b]=1
timer=2  вход c   tin[c]=2
timer=3  вход d   tin[d]=3
timer=4  выход d  tout[d]=4      (у d соседей нет)
timer=5  выход c  tout[c]=5
timer=6  выход b  tout[b]=6
         из a смотрим ребро a→d: d ЧЁРНАЯ, не идём
timer=7  выход a  tout[a]=7

Отрезки: a: [0,7], b: [1,6], c: [2,5], d: [3,4]. Все вложены друг в друга - так и должно быть, ведь обход шёл цепочкой. Проверим правило предка: a предок d? 0 < 3 и 4 < 7 - да. А d предок a? 3 < 0 неверно - нет. Теперь важная тонкость: b - предок d В ДЕРЕВЕ ОБХОДА (1 < 3 и 4 < 6 - да), хотя в графе ребра b→d нет; дерево обхода отражает ПУТЬ, по которому обход добрался до вершины, а не структуру графа.

Разбор: почему скобки не пересекаются частично

Докажем от противного. Пусть отрезки пересекаются частично: tin[u] < tin[v] < tout[u] < tout[v]. Читаем это как события: вошли в u, потом вошли в v, потом ВЫШЛИ из u, и только потом вышли из v.

Но выход из u происходит в тот момент, когда закончился её вызов dfs(u). А вход в v случился ПОЗЖЕ входа в u и РАНЬШЕ выхода из u, то есть внутри вызова dfs(u). Значит dfs(v) был вызван изнутри dfs(u) - прямо или через цепочку вложенных вызовов. Вложенный вызов не может пережить объемлющий: dfs(u) не вернётся, пока не вернулись все вызовы, которые он породил. Получается tout[v] < tout[u], что противоречит предположению.

Отсюда и практическая польза. Раз частичного пересечения не бывает, то из tin[u] < tin[v] следует ровно одно из двух: либо v внутри u (потомок), либо отрезки разошлись и v лежит в другой ветви. Различает их одно сравнение - tout[v] < tout[u]. Эти два числа заменяют подъём по родителям, который стоил бы O(глубины); дальше в разделе на них будут стоять и поиск мостов, и запросы к дереву.

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

Первое: заводить отдельные счётчики для входа и выхода. Сама проверка предка при этом уцелеет - она сравнивает tin с tin и tout с tout, - но картинка «отрезки на одной шкале» и теорема о скобках развалятся, а вместе с ними и все рассуждения, где tin сравнивают с tout (например, «вершина ещё не вышла, значит она серая»). Проще и надёжнее держать один счётчик. Второе: сравнивать времена вершин из РАЗНЫХ запусков обхода (разных компонент) как предков и потомков. Формально отрезки разных компонент не пересекаются, и правило даёт верный ответ «не предок», но путаница здесь частая: вершины из разных компонент вообще не связаны деревом. Третье: считать, что tin меньше означает «ближе к корню». Нет: tin меньше у той вершины, в которую вошли раньше, а она может лежать в другой ветви. Правило предка требует ОБОИХ сравнений. Четвёртое: путать чёрную вершину с серой при поиске цикла - об этом целиком следующий урок, и это самая частая ошибка темы. Пятое: хранить цвета строками, как в примере выше, - для чтения хорошо, для скорости берут числа 0/1/2.

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

Времена входа и выхода - это способ превратить обход в ИНДЕКС, по которому потом отвечают быстро. Проверка «лежит ли вершина в поддереве» за O(1) - основа для запросов к дереву: по такому же приёму работает сведение дерева к массиву (эйлеров обход), на котором строятся запросы «наименьший общий предок» и суммы по поддереву. Порядок ВЫХОДА из вершин, если его перевернуть, даёт топологическую сортировку - следующая глава. Времена входа плюс «минимально достижимое время» дают мосты и точки сочленения. В реальном коде тот же приём встречается под другим именем: вложенные интервалы - это способ хранить иерархию в реляционной базе (модель nested sets), где «все потомки узла» достаются одним запросом WHERE left BETWEEN ... AND ... без рекурсии. Это тот же самый tin/tout.

Теперь сам

Неориентированный граф: 1-2, 1-3, 2-4, 3-4. Обход стартует из вершины 1, соседи перебираются по возрастанию номера. Выпиши tin и tout всех вершин и ответь: является ли вершина 2 предком вершины 3 в дереве обхода?