Мосты и точки сочленения

В неориентированном графе:

Мост — ребро, при удалении которого число компонент связности увеличивается.

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

Наивно и то, и другое ищется перебором: удалить и пересчитать компоненты, $O(m(n+m))$ и $O(n(n+m))$. Обе задачи решаются одним обходом за $O(n + m)$, причём почти одинаково.

Величина up

Подвесим дерево обхода и введём две величины для каждой вершины:

• $h_v$ — глубина вершины в дереве обхода;
• $up_v$ — минимальная глубина, которой можно достичь, если из $v$ спуститься вниз по древесным рёбрам сколько угодно раз (в том числе ноль) и затем ровно один раз подняться по обратному ребру.

Рекуррентность прямо из определения. Из $v$ можно:

• никуда не идти: получаем $h_v$;
• сразу подняться по обратному ребру в $u$: получаем $h_u$;
• спуститься в ребёнка $to$ и там повторить выбор: получаем $up_{to}$.

$$up_v = \min\Bigl(h_v,\; \min_{\text{обратное } v \to u} h_u,\; \min_{\text{ребёнок } to} up_{to}\Bigr)$$

Обратите внимание на асимметрию: для обратных рёбер берётся $h_u$, для детей — $up_{to}$. Перепутать их — самая частая ошибка, и формулу стоит не заучивать, а уметь выводить из определения.

Критерии

Ребро $v \to to$ (древесное) — мост, если $up_{to} > h_v$.

Смысл: из поддерева $to$ нельзя подняться выше $v$, даже спустившись как угодно глубоко. Значит, кроме этого ребра, никакого пути из поддерева наружу нет, и удаление его разрывает граф.

Если $up_{to} \le h_v$, то есть обходной путь, и ребро не мост.

Вершина $v$ (не корень) — точка сочленения, если у неё есть ребёнок $to$ с $up_{to} \ge h_v$.

Разница в одном знаке. Для моста нужно строго выше $v$; для точки сочленения достаточно, чтобы поддерево не могло подняться выше самой $v$ — если максимум, куда оно дотягивается, это сама $v$, то удаление $v$ отрезает поддерево.

Корень — точка сочленения, если у него больше одного ребёнка в дереве обхода.

Корень приходится разбирать отдельно: для него $up_{to} \ge h_{root}$ выполняется всегда, потому что $h_{root}$ — минимальная глубина. Без особого случая код объявил бы корень точкой сочленения в любом графе.

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

Код

vector<int> h, up;
set<pair<int, int>> bridges;
set<int> cutpoints;

void dfs(int v, int parent) {
    up[v] = h[v];
    int children = 0;
    bool skippedParent = false;
    for (int to : g[v]) {
        if (to == parent && !skippedParent) { skippedParent = true; continue; }
        if (h[to] != -1) {
            up[v] = min(up[v], h[to]);          // обратное ребро
        } else {
            h[to] = h[v] + 1;
            dfs(to, v);
            children++;
            up[v] = min(up[v], up[to]);         // ребёнок
            if (up[to] > h[v]) bridges.insert({min(v, to), max(v, to)});
            if (parent != -1 && up[to] >= h[v]) cutpoints.insert(v);
        }
    }
    if (parent == -1 && children > 1) cutpoints.insert(v);
}

// в main:
h.assign(n, -1);
up.assign(n, -1);
for (int v = 0; v < n; v++)
    if (h[v] == -1) { h[v] = 0; dfs(v, -1); }

Проверено: на двадцати тысячах случайных графов до восьми вершин множество мостов и множество точек сочленения совпали с прямым перебором — удалить ребро (вершину) и пересчитать компоненты.

Ловушка с кратными рёбрами

Флаг skippedParent — не украшение. Ребро в родителя нужно пропустить ровно один раз.

Если между $v$ и родителем два ребра, то это цикл длины 2, и ни одно из них не мост. Наивная проверка if (to == parent) continue; пропустит оба и объявит ребро мостом — неверно.

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

Петли на мосты и точки сочленения не влияют вовсе, но их стоит отфильтровать при чтении, чтобы не мешались.

Разница между двумя понятиями

Их легко перепутать, а связь между ними не такая прямая, как кажется.

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

И наоборот, точка сочленения может не быть концом моста: две «восьмёрки», склеенные в одной вершине, дают точку сочленения без единого моста.

Поэтому вычислять одно через другое нельзя — но, к счастью, обе величины считаются одним и тем же обходом.