Конспект: мосты, точки сочленения, двусвязность

Понятия

Мост - ребро, удаление которого увеличивает число компонент. Точка сочленения - вершина, удаление которой (с её рёбрами) увеличивает число компонент.

low[v] - минимальное время входа, достижимое из поддерева v при спуске по древесным рёбрам и не более чем ОДНОМ подъёме по обратному ребру:

low[v] = min( tin[v],
              tin[u]  по обратным рёбрам v → u,     ← именно tin, не low
              low[c]  по детям c в дереве обхода )

Двусвязность: рёберная - нет мостов; вершинная - нет точек сочленения (и вершин больше двух). Вершинная строго сильнее. По теореме Менгера равносильно двум путям без общих рёбер (без общих внутренних вершин).

Блок - максимальный вершинно-двусвязный кусок; блоки пересекаются по точкам сочленения и образуют дерево блоков. Каждый мост - блок из двух вершин.

Что унести

разница > и >= - это разница между «оторвать ребро» и «выдернуть вершину»

Наивная проверка каждого ребра стоит O(E·(V+E)); один обход с low даёт все ответы за O(V + E).

Тихие ошибки: пропускать родителя по номеру ВЕРШИНЫ (кратные рёбра дают ложные мосты); брать по обратному ребру low[u] вместо tin[u] (это второй подъём); применять к корню общее правило; считать, что отсутствие мостов означает отсутствие точек сочленения (два треугольника с общей вершиной); ждать, что концы моста всегда критичны (висячая вершина - нет).

Общий приём, который стоит унести шире темы: обход в глубину умеет считать агрегат по поддереву, и агрегат, вычисленный при возврате из рекурсии, отвечает на вопросы про структуру целиком. Поменял неравенство - получил другую задачу; добавил стек вершин - получил компоненты.

Куда это ведёт

Следующая глава - запросы к дереву: наименьший общий предок и минимум на отрезке, где времена входа-выхода снова становятся главным инструментом.