Поиск мостов

Определение. Мостом называется ребро, при удалении которого связный неориентированный граф становится несвязным.

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

Наивный алгоритм поочередного удаления каждого ребра \((u, v)\) и проверки наличия пути \(u \leadsto v\) потребует \(O(m^2)\) операций. Чтобы научиться находить мосты быстрее, сначала сформулируем несколько утверждений, связанных с обходом в глубину.

Запустим DFS из произвольной вершины. Введем новые виды рёбер:

• Прямые рёбра — те, по которым были переходы в dfs.
• Обратные рёбра — то, по которым не было переходов в dfs.

Заметим, что никакое обратное ребро \((u, v)\) не может являться мостом: если его удалить, то всё равно будет существовать какой-то путь от \(u\) до \(v\), потому что подграф из прямых рёбер является связным деревом.

Значит, остается только проверить все прямые рёбра. Это уже немного лучше — такой алгоритм будет работать за \(O(n m)\).

Сооптимизировать его до линейного времени (до одного прохода dfs) поможет замечание о том, что обратные рёбра могут вести только «вверх» — к какому-то предку в дереве обхода графа, но не в другие «ветки» — иначе бы dfs увидел это ребро раньше, и оно было бы прямым, а не обратным.

Тогда, чтобы определить, является ли прямое ребро \(v \to u\) мостом, мы можем воспользоваться следующим критерием: глубина \(h_v\) вершины \(v\) меньше, чем минимальная глубина всех вершин, соединенных обратным ребром с какой-либо вершиной из поддерева \(u\).

Для ясности, обозначим эту величину как \(d_u\), которую можно считать во время обхода по следующей формуле\[ d_v = \min \begin{cases} h_v, &\\ d_u, &\text{ребро } (v \to u) \text{ прямое} \\ h_u, &\text{ребро } (v \to u) \text{ обратное} \end{cases} \]

Если это условие (\(h_v < d_u\)) не выполняется, то существует какой-то путь из \(u\) в какого-то предка \(v\) или саму \(v\), не использующий ребро \((v, u)\), а в противном случае — наоборот.

const int maxn = 1e5;

bool used[maxn];
int h[maxn], d[maxn];

void dfs(int v, int p = -1) {
    used[u] = true;
    d[v] = h[v] = (p == -1 ? 0 : h[p] + 1);
    for (int u : g[v]) {
        if (u != p) {
            if (used[u]) // если рябро обратное
                d[v] = min(d[v], h[u]);
            else { // если рябро прямое
                dfs(u, v);
                d[v] = min(d[v], d[u]);
                if (h[v] < d[v]) {
                    // ребро (v, u) -- мост
                }
            }
        }
    }
}

Примечание. Более известен алгоритм, вместо глубин вершин использующий их \(tin\), но автор считает его чуть более сложным для понимания.