Мосты

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

Пусть нам дан неориентированный граф без петель и кратных рёбер.

Будем искать мосты в графе с помощью обхода в глубину.

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

Заметим, что обратное ребро мостом быть не может, так как все равно останется путь по прямым ребрам.

Для того, чтобы определить является ли прямое ребро $(v, u)$ мостом, нам нужно проверить, что из поддерева $u$ нет ни одного обратного ребра, которое соединяется с вершиной, глубина которой меньше, чем глубина вершины $v$.

Действительно, если такое обратное ребро есть, то после удаления ребра $(v, u)$, поддерево $u$ все равно будет “подвешено” к основному дереву.

Чтобы быстро понимать, есть ли такое обратное ребро, будем для каждой вершины поддерживать $f_{up}[v]$ - минимальную глубину среди вершин, соединенных обратным ребром с вершинами из поддерева $v$.

Будем пересчитывать эту динамику во время обхода в глубину

\[f_{up}[v] = \min \begin{cases} h[v] \\ f_{up}[u] \text{, если ребро } (v, u) \text{ - прямое} \\ h[u] \text{, если ребро } (v, u) \text{ - обратное} \end{cases}\]

Тогда, если для какого-то прямого ребра $(v, u)$ выполняется неравенство $f_{up}[u] > h[v]$, то это ребро является мостом.

Обычно, $h[v]$ заменяют на $tin[v]$ (время входа dfs в вершину), потому что его проще поддерживать, а необходимые свойства сохраняются.

vector<vector<int>> g;
vector<int> used;
vector<int> tin, fup;
int timer = 0;

vector<pair<int, int>> ans;


void dfs(int v, int p = -1) {
    used[v] = 1;
    tin[v] = fup[v] = timer++;
    int cnt = 0;

    for (auto u: g[v]) {
        if (u == p) {
             continue;
        }
        
        if (used[u]) {  // обратное ребро
            fup[v] = min(fup[v], tin[u]);
        } else {  // прямое ребро
            dfs(u, v);
            fup[v] = min(fup[v], fup[u]);
            if (tin[v] < fup[u]) {
                ans.emplace_back(v, u);
            }
        }
    }
}

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

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

Точки сочленения ищутся почти так же, как мосты.

Есть лишь два отличия:

1. Критерий того, что $v$ - точка сочленения это то, что $f_{up}[u] \geq h[v]$ для какого-то её сына $u$.
2. Для корня такой способ не подойдёт, ведь у корня по определению минимальная высота. Для корня критерием будет количество сыновей: если их больше 1, то корень - точка сочленения, иначе - нет.

vector<vector<int>> g;
vector<int> used;
vector<bool> ans;
vector<int> tin, fup;
int timer = 0;


void dfs(int v, int p = -1) {
    used[v] = 1;
    tin[v] = fup[v] = timer++;
    int cnt = 0;

    for (auto u: g[v]) {
        if (v == u) {
            continue;
        }
        if (used[u]) {
            fup[v] = min(fup[v], tin[u]);
        } else {
            dfs(u, v);
            fup[v] = min(fup[v], fup[u]);
            if (fup[u] >= tin[v] && p != -1) {
                ans[v] = true;
            }
            cnt++;
        }
    }
    if (p == -1 && cnt > 1) {
        ans[v] = true;
    }
}