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

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

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

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

Наивный алгоритм поочередного удаления каждого ребра $(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$, которую можно считать во время обхода по следующей формуле:

Если это условие ($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[v] = 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[u]) {
                    // если нельзя другим путем добраться в v или выше,
                    // то ребро (v, u) -- мост
                }
            }
        }
    }
}

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

#Точки сочленения

Задача поиска точек сочленения не сильно отличается от задачи поиска мостов.

Вершина $v$ является точкой сочленения, когда из какого-то её ребёнка $u$ нельзя дойти до её предка, не используя ребро $(v, u)$. Для конкретного прямого ребра $v \to u$ этот факт можно проверить так: $h_v \leq d_u$ (теперь неравенство нестрогое, так как если из вершины можно добраться только до нее самой, то она все равно будет точкой сочленения).

Используя этот факт, можно оставить алгоритм практически прежним — нужно проверить этот критерий для всех прямых рёбер $v \to u$:

void dfs(int v, int p = -1) {
    used[v] = 1;
    d[v] = h[v] = (p == -1 ? 0 : h[p] + 1);
    int children = 0;
    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[u] && p != -1) { // корень (p == -1) обрабатываем отдельно
                    // v -- точка сочленения
                    // (это условие может выполниться много раз для разных детей)
                }
              	children++;
            }
        }
    }
    if (p == -1 && children > 1) {
        // v -- корень и точка сочленения
    }
}

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