Encontrar puentes en un grafo en $O(N+M)$

Se da un grafo no dirigido. Un puente se define como una arista que, al eliminarla, deja el grafo desconexo (o, más precisamente, aumenta el número de componentes conexas del grafo). La tarea es encontrar todos los puentes del grafo dado.

De manera informal, el problema se formula así: dado un mapa de ciudades conectadas por carreteras, encontrar todas las carreteras “importantes”, es decir, aquellas que, al eliminarlas, hacen desaparecer un camino entre algún par de ciudades.

El algoritmo descrito aquí se basa en la búsqueda en profundidad y tiene complejidad $O(N+M)$ , donde $N$ es el número de vértices y $M$ es el número de aristas del grafo.

Nótese que también existe el artículo Encontrar puentes online: a diferencia del algoritmo offline descrito aquí, el algoritmo online es capaz de mantener la lista de todos los puentes en un grafo que cambia (suponiendo que el único tipo de cambio es la adición de aristas nuevas).

Algoritmo

Elegimos un vértice arbitrario del grafo $root$ y ejecutamos una búsqueda en profundidad desde él. Observemos el siguiente hecho (fácil de demostrar):

Supongamos que estamos en el DFS, recorriendo las aristas que salen del vértice $v$ . La arista actual $(v, to)$ es un puente si y solo si ninguno de los vértices $to$ y sus descendientes en el árbol de recorrido DFS tiene una arista de retroceso hacia el vértice $v$ o hacia alguno de sus ancestros. En efecto, esta condición significa que no hay otra forma de ir de $v$ a $to$ excepto por la arista $(v, to)$ .

Ahora hay que aprender a comprobar este hecho de forma eficiente para cada vértice. Usaremos el “tiempo de entrada al nodo” calculado por la búsqueda en profundidad.

Así, sea $\mathtt{tin}[v]$ el tiempo de entrada del nodo $v$ . Introducimos un arreglo $\mathtt{low}$ que nos permitirá almacenar el menor tiempo de entrada de un nodo alcanzado en la búsqueda DFS al que un nodo $v$ puede llegar mediante una sola arista desde sí mismo o desde sus descendientes. $\mathtt{low}[v]$ es el mínimo entre $\mathtt{tin}[v]$ , los tiempos de entrada $\mathtt{tin}[p]$ de cada nodo $p$ conectado con el nodo $v$ mediante una arista de retroceso $(v, p)$ y los valores de $\mathtt{low}[to]$ de cada vértice $to$ que es descendiente directo de $v$ en el árbol DFS:

$\mathtt{low}[v] = \min \left{$

Ahora, hay una arista de retroceso desde el vértice $v$ o uno de sus descendientes hacia uno de sus ancestros si y solo si el vértice $v$ tiene un hijo $to$ para el cual $\mathtt{low}[to] \leq \mathtt{tin}[v]$ . Si $\mathtt{low}[to] = \mathtt{tin}[v]$ , la arista de retroceso llega directamente a $v$ ; en caso contrario, llega a uno de los ancestros de $v$ .

Así, la arista actual $(v, to)$ del árbol DFS es un puente si y solo si $\mathtt{low}[to] > \mathtt{tin}[v]$ .

Implementación

La implementación necesita distinguir tres casos: cuando bajamos por la arista en el árbol DFS, cuando encontramos una arista de retroceso hacia un ancestro del vértice y cuando volvemos al padre del vértice. Estos son los casos:

$\mathtt{visited}[to] = false$ - la arista forma parte del árbol DFS;
$\mathtt{visited}[to] = true$ && $to \neq parent$ - la arista es una arista de retroceso hacia uno de los ancestros;
$to = parent$ - la arista vuelve al padre en el árbol DFS.

Para implementar esto, necesitamos una función de búsqueda en profundidad que reciba el vértice padre del nodo actual.

En el caso de aristas múltiples, hay que tener cuidado al ignorar la arista que viene del padre. Para resolver este problema, podemos agregar un flag parent_skipped que garantiza que solo omitimos al padre una vez.


void IS_BRIDGE(int v,int to); // alguna función para procesar el puente encontrado
int n; // cantidad de nodos
vector<vector<int>> adj; // lista de adyacencia del 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++;
    bool parent_skipped = false;
    for (int to : adj[v]) {
        if (to == p && !parent_skipped) {
            parent_skipped = true;
            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);
    }
}

La función principal es find_bridges; realiza la inicialización necesaria y arranca la búsqueda en profundidad en cada componente conexa del grafo.

La función IS_BRIDGE(a, b) es alguna función que procesará el hecho de que la arista $(a, b)$ es un puente; por ejemplo, la imprime.

Nótese que esta implementación falla si el grafo tiene aristas múltiples, porque las ignora. Por supuesto, las aristas múltiples nunca formarán parte de la respuesta, así que IS_BRIDGE puede comprobar además que el puente reportado no es una arista múltiple. Como alternativa, se puede pasar a dfs el índice de la arista usada para entrar al vértice en lugar del vértice padre (y almacenar los índices de todos los vértices).

Problemas de práctica

UVA #796 “Critical Links” [dificultad: baja]
UVA #610 “Street Directions” [dificultad: media]
Case of the Computer Network (Codeforces Round #310 Div. 1 E) [dificultad: alta]

Encontrar puentes en un grafo en O(N+M)O(N+M)O(N+M)

Algoritmo

Implementación

Problemas de práctica

Encontrar puentes en un grafo en $O(N+M)$