Localizando pontes em um grafo em $O(N+M)$

Seja um grafo não direcionado. Uma ponte é definida como uma aresta que, quando removida, desconecta o grafo (ou mais precisamente, aumenta o número de componentes conectados no grafo). A tarefa é encontrar todas as pontes no grafo fornecido.

Informalmente, o problema é formulado da seguinte maneira: dado um mapa de cidades conectadas com estradas, encontre todas as estradas "importantes", isto é, estradas que, quando removidas, causam o desaparecimento de um caminho entre alguns pares de cidades.

O algoritmo descrito aqui é baseado em uma DFS e tem complexidade $O(N+M)$, onde $N$ é o número de vértices e $M$ é o número de arestas no grafo.

Também há o artigo encontrando pontes online - diferentemente do algoritmo offline descrito aqui, o algoritmo online é capaz de manter a lista de todas as pontes em um grafo em constante mudança (supondo que o único tipo de mudança seja a adição de novas arestas).

Algoritmo

Escolha um vértice arbitrário do grafo $raiz$ e execute uma DFS a partir dele. Observe que:

Agora temos que aprender a verificar esse fato para cada vértice com eficiência. Usaremos o "tempo de entrada" do nó calculado pela DFS.

Então, seja $tin[v]$ o tempo de entrada para o nó $v$. Introduzimos uma array $low$ que nos permitirá verificar o fato para cada vértice $v$. $low[v]$ é o mínimo de $tin[v]$, os tempos de entrada $tin[p]$ para cada nó $p$ que está conectado ao nó $v$ por uma back-edge $(v, p)$ e os valores de $low[to]$ para cada vértice $to$ que é um descendente direto de $v$ na árvore da DFS:

$$low[v] = \min \begin{cases} tin[v] \\ tin[p]& \text{ para todo }p\text{ em que }(v, p)\text{ back edge} \\ low[to]& \text{ para todo }to\text{ em que }(v, to)\text{ tree edge} \end{cases}$$

Agora, há uma back edge do vértice $v$ ou de um de seus descendentes para um de seus ancestrais se, e somente se, o vértice $v$ tiver um filho $to$ pelo qual $low[to] \leq tin[v]$. Se $low[to] = tin[v]$, a back edge vai diretamente em $v$, caso contrário, vai para um dos ancestrais de $v$.

Portanto, a aresta atual $(v, to)$ na árvore da DFS é uma ponte se, e somente se, $low[to] > tin[v]$.

Implementação

A implementação precisa distinguir três casos: quando descemos na aresta da árvore da DFS, quando encontramos uma back edge para um ancestral do vértice e quando retornamos a um parente de um vértice. Casos:

Para implementar isso, precisamos de uma função DFS que aceita o vértice parente do nó atual.

Implementação em C++:

int n; // número de nós
vector<vector<int>> adj; // lista de adjacência - grafo

vector<bool> visited;
vector<int> tin, low;
int timer;

void dfs(int v, int p = -1) {
    visited[v] = true;
    tin[v] = low[v] = timer++;
    for (int to : adj[v]) {
        if (to == p) continue;
        if (visited[to]) {
            low[v] = min(low[v], tin[to]);
        } else {
            dfs(to, v);
            low[v] = min(low[v], low[to]);
            if (low[to] > tin[v])
                IS_BRIDGE(v, to);
        }
    }
}

void find_bridges() {
    timer = 0;
    visited.assign(n, false);
    tin.assign(n, -1);
    low.assign(n, -1);
    for (int i = 0; i < n; ++i) {
        if (!visited[i])
            dfs(i);
    }
}

A função principal é find_bridges; ela executa uma inicialização necessária e inicializa a DFS em cada componente conectado do grafo.

A função IS_BRIDGE(a, b) é uma função que processará o fato de que a aresta $(a, b)$ é uma ponte, por exemplo, printando a aresta.

Esta implementação não funciona corretamente se o grafo tiver arestas múltiplas(multiple edges), pois as ignora. Obviamente, essas arestas nunca farão parte da resposta, portanto IS_BRIDGE pode verificar adicionalmente se a ponte relatada não é uma aresta múltipla. Como alternativa, é possível passar para a dfs o índice da aresta usada para entrar no vértice em vez do vértice parente (e armazenar o índice de todos os vértices).

Problemas