Рёберная двусвязность

Продолжение мостов. Приём простой, а последствия у него большие.

Построение

1. Найти все мосты.
2. Мысленно удалить их и найти компоненты связности оставшегося графа.
3. Сжать каждую компоненту в одну вершину.
4. Вернуть мосты — теперь как рёбра между сжатыми вершинами.

Получится дерево.

Связность сохранилась: мы ничего не выбрасывали насовсем. А циклов не осталось: будь цикл из мостов, ни одно ребро этого цикла не было бы мостом — при его удалении обход прошёл бы по остатку цикла.

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

flowchart LR
    subgraph было
    A1(( )) --- A2(( ))
    A2 --- A3(( ))
    A3 --- A1
    A3 --- B1(( ))
    B1 --- B2(( ))
    B2 --- B3(( ))
    B3 --- B1
    end

Здесь два треугольника, соединённые единственным ребром. Это ребро — мост; после сжатия получается дерево из двух вершин и одного ребра.

Реализация

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

vector<int> comp(n, -1);
int c = 0;

void paint(int v, int c) {
    comp[v] = c;
    for (int to : g[v]) {
        if (comp[to] != -1) continue;
        if (isBridge(v, to)) continue;   // через мост не идём
        paint(to, c);
    }
}

// в main, после поиска мостов:
for (int v = 0; v < n; v++)
    if (comp[v] == -1) paint(v, c++);

// дерево компонент
vector<vector<int>> tree(c);
for (auto& [u, v] : bridges) {
    tree[comp[u]].push_back(comp[v]);
    tree[comp[v]].push_back(comp[u]);
}

Проверять принадлежность ребра множеству мостов удобнее по номеру ребра, а не по паре вершин: с кратными рёбрами пара неоднозначна.

Всё вместе — $O(n + m)$: поиск мостов, покраска, построение дерева.

Зачем это нужно

Смысл приёма в том, что задача на произвольном графе превращается в задачу на дереве, а на деревьях умеют гораздо больше.

Задача про платные дороги. Проезд по ребру стоит монету, если существует пара городов, между которыми любой маршрут проходит по этому ребру; иначе бесплатно. Сколько монет нужно, чтобы гарантированно доехать между любой парой городов?

Платные рёбра — это ровно мосты. Сжимаем, получаем дерево, и ответ — диаметр этого дерева: худшая пара городов лежит на его концах.

Сколько пар маршрутов проходит через мост. После сжатия мост — ребро дерева; удалив его, получим две части. Ответ — произведение числа исходных вершин в одной части на число в другой. В исходном графе такой вопрос выглядит безнадёжно, в дереве считается одним обходом.

Добавить минимум рёбер, чтобы мостов не осталось. В дереве компонент считаем число листьев $L$; ответ — $\lceil L / 2 \rceil$. Соединяем листья попарно, и все рёбра перестают быть мостами.

Вершинная двусвязность

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

Асимметрия терминологии сбивает с толку, и запомнить её стоит:

	что разбивается	что разделяет
рёберная двусвязность	вершины	мосты
вершинная двусвязность	рёбра	точки сочленения

Строится вершинная двусвязность похоже, через точки сочленения, но сжимать сложнее: одна вершина может принадлежать нескольким компонентам сразу. Результат называется блок-дерево.

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