Хрупкие мосты — разбор задачи

1. Идея

Нужно посчитать количество мостов в неориентированном графе.

Мостом называется ребро, удаление которого увеличивает число компонент связности. Иначе говоря, если удалить такую дорогу, какая-то часть поселений станет недостижимой из другой.

Классический способ найти все мосты — обход графа в глубину и вычисление двух массивов:

• tin[v] — время входа в вершину v;
• low[v] — минимальное время входа, достижимое из v по:
  • нулю или более рёбрам дерева DFS вниз,
  • и, возможно, одному обратному ребру вверх.

Если для ребра дерева DFS p -> v выполняется low[v] > tin[p], то это ребро — мост.

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

2. Наблюдения

Наблюдение 1. Когда ребро не является мостом

Если из поддерева вершины v можно попасть в вершину p или ещё выше по дереву DFS не только через ребро p - v, то после удаления ребра p - v связность не нарушится.

Это означает, что существует обходной путь, и ребро не мост.

Наблюдение 2. Что означает low[v]

low[v] — это минимальное значение tin, которое можно достичь из вершины v, если:

• идти вниз по рёбрам DFS,
• а потом, возможно, один раз подняться по обратному ребру.

Если low[v] <= tin[p], то из поддерева v есть путь к p или выше, значит ребро p - v не мост.

Если же low[v] > tin[p], то поддерево v никак не соединяется с предками p, кроме как через ребро p - v. Значит, это мост.

Наблюдение 3. Граф может быть несвязным

Нельзя запускать DFS только из вершины 1. Нужно пройти по всем вершинам и для каждой ещё не посещённой запускать новый обход.

Наблюдение 4. Почему нужен итеративный DFS

При n = 200000 рекурсивный DFS может переполнить стек вызовов. Поэтому используется собственный стек st, в котором хранятся вершины текущего пути обхода.

3. Алгоритм

Построим список смежности.

Будем хранить:

• tin[v] — время входа;
• low[v] — минимальное достижимое время;
• parent[v] — родителя в дереве DFS;
• it[v] — индекс следующего соседа, которого ещё не обработали;
• timer — счётчик времени;
• bridges — количество мостов.

Дальше для каждой вершины start:

• если она уже посещена, пропускаем;
• иначе начинаем итеративный DFS из неё.

Как работает стек

Пусть в стеке лежит вершина v.

1. Если мы зашли в неё впервые, задаём:

   • tin[v] = low[v] = ++timer.

2. Если у v ещё есть необработанные соседи:

   • берём очередного соседа to;
   • если to == parent[v], пропускаем;
   • если to ещё не посещён, делаем его ребёнком:
     • parent[to] = v,
     • кладём to в стек;
   • иначе это обратное ребро, обновляем:
     • low[v] = min(low[v], tin[to]).

3. Если все соседи обработаны, значит завершаем вершину:

   • убираем её из стека;
   • если у неё есть родитель p:
     • если low[v] > tin[p], увеличиваем число мостов;
     • обновляем low[p] = min(low[p], low[v]).

После завершения всех обходов выводим bridges.

4. Почему это работает

Докажем корректность.

Что хранит tin

При первом посещении вершины v ей присваивается уникальное время входа tin[v]. Чем раньше посещена вершина, тем меньше её tin.

Что хранит low

После полной обработки вершины v значение low[v] равно минимальному tin среди:

• самой вершины v,
• всех вершин, достижимых из поддерева v по рёбрам DFS вниз,
• вершин, в которые можно попасть из этого поддерева одним обратным ребром.

Это верно, потому что:

• при встрече обратного ребра v -> to обновляется low[v] через tin[to];
• после завершения ребёнка to значение low[to] передаётся родителю v.

Значит, к моменту выхода из вершины v в low[v] уже собрана вся нужная информация о её поддереве.

Критерий моста

Рассмотрим ребро дерева DFS p - v, где p = parent[v].

Случай 1: low[v] > tin[p]

Это означает, что из поддерева v нельзя попасть ни в p, ни в какого-либо предка p обратным ребром. Значит, единственная связь этого поддерева с остальным графом — ребро p - v.

Если удалить его, поддерево v отделится. Следовательно, это мост.

Случай 2: low[v] <= tin[p]

Это означает, что из поддерева v существует путь к p или выше, не использующий ребро p - v как единственный способ связи. Тогда после удаления p - v вершины всё ещё останутся связными через обходной путь.

Следовательно, это не мост.

Таким образом, условие low[v] > tin[p] точно и только тогда определяет мост.

Почему рассматриваются все компоненты

Так как граф может быть несвязным, мы запускаем обход из каждой непосещённой вершины. Поэтому каждая вершина и каждое ребро будут обработаны в своей компоненте связности, и ни один мост не потеряется.

5. Сложность

Пусть n — число вершин, m — число рёбер.

• Построение графа: O(m)
• Весь обход: O(n + m)

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

Итоговая сложность: O(n + m)

Память:

• список смежности,
• несколько массивов длины n.

Итого: O(n + m)

6. Код на C++17

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int n, m;
    cin >> n >> m;

    vector<vector<int>> g(n + 1);
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    vector<int> tin(n + 1, 0), low(n + 1, 0), parent(n + 1, -1), it(n + 1, 0);
    int timer = 0;
    long long bridges = 0;

    for (int start = 1; start <= n; start++) {
        if (tin[start] != 0) continue;

        vector<int> st;
        st.push_back(start);
        parent[start] = -1;

        while (!st.empty()) {
            int v = st.back();

            if (tin[v] == 0) {
                ++timer;
                tin[v] = low[v] = timer;
            }

            if (it[v] < (int)g[v].size()) {
                int to = g[v][it[v]];
                it[v]++;

                if (to == parent[v]) continue;

                if (tin[to] == 0) {
                    parent[to] = v;
                    st.push_back(to);
                } else {
                    if (tin[to] < low[v]) low[v] = tin[to];
                }
            } else {
                st.pop_back();
                if (parent[v] != -1) {
                    int p = parent[v];
                    if (low[v] > tin[p]) bridges++;
                    if (low[v] < low[p]) low[p] = low[v];
                }
            }
        }
    }

    cout << bridges << '\n';
    return 0;
}

7. Код на Python 3

n, m = map(int, input().split())

g = [[] for _ in range(n + 1)]
for _ in range(m):
    u, v = map(int, input().split())
    g[u].append(v)
    g[v].append(u)

tin = [0] * (n + 1)
low = [0] * (n + 1)
parent = [-1] * (n + 1)
it = [0] * (n + 1)

timer = 0
bridges = 0

for start in range(1, n + 1):
    if tin[start] != 0:
        continue

    st = [start]
    parent[start] = -1

    while st:
        v = st[-1]

        if tin[v] == 0:
            timer += 1
            tin[v] = timer
            low[v] = timer

        if it[v] < len(g[v]):
            to = g[v][it[v]]
            it[v] += 1

            if to == parent[v]:
                continue

            if tin[to] == 0:
                parent[to] = v
                st.append(to)
            else:
                if tin[to] < low[v]:
                    low[v] = tin[to]
        else:
            st.pop()
            if parent[v] != -1:
                p = parent[v]
                if low[v] > tin[p]:
                    bridges += 1
                if low[v] < low[p]:
                    low[p] = low[v]

print(bridges)