Encontrar puentes de forma online

Nos dan un grafo no dirigido. Un puente es una arista cuya eliminación hace que el grafo deje de ser conexo (o, más precisamente, aumenta el número de componentes conexas). Nuestra tarea es encontrar todos los puentes del grafo dado.

De forma informal esta tarea se puede plantear así: tenemos que encontrar todos los caminos “importantes” en el mapa de carreteras dado, es decir, aquellos caminos cuya eliminación hará que algunas ciudades dejen de ser alcanzables desde otras.

Ya existe el artículo Encontrar puentes en $O(N+M)$ que resuelve esta tarea con un recorrido de Búsqueda en Profundidad. Este algoritmo será mucho más complicado, pero tiene una gran ventaja: el algoritmo descrito en este artículo funciona de forma online, lo que significa que el grafo de entrada no tiene que conocerse de antemano. Las aristas se agregan de a una, y después de cada adición el algoritmo vuelve a contar todos los puentes del grafo actual. En otras palabras, el algoritmo está diseñado para trabajar de forma eficiente sobre un grafo dinámico, que cambia.

De forma más rigurosa, el enunciado del problema es el siguiente: Inicialmente el grafo está vacío y consiste de $n$ vértices. Luego recibimos pares de vértices $(a, b)$, que denotan una arista agregada al grafo. Después de cada arista recibida, es decir, después de agregar cada arista, imprimir el número actual de puentes en el grafo.

También es posible mantener una lista de todos los puentes y además soportar de forma explícita las componentes 2-arista-conexas.

El algoritmo descrito abajo funciona en tiempo $O(n \log n + m)$, donde $m$ es el número de aristas. El algoritmo se basa en la estructura de datos Union-Find / conjuntos disjuntos (DSU). Sin embargo, la implementación de este artículo toma tiempo $O(n \log n + m \log n)$, porque usa la versión simplificada del DSU sin unión por rango.

Algoritmo

Primero definamos una componente $k$-arista-conexa: es una componente conexa que permanece conexa siempre que se quiten menos de $k$ aristas.

Es muy fácil ver que los puentes particionan el grafo en componentes 2-arista-conexas. Si comprimimos cada una de esas componentes 2-arista-conexas en vértices y solo dejamos los puentes como aristas en el grafo comprimido, entonces obtenemos un grafo acíclico, es decir, un bosque.

El algoritmo descrito abajo mantiene este bosque de forma explícita, así como las componentes 2-arista-conexas.

Es claro que inicialmente, cuando el grafo está vacío, contiene $n$ componentes 2-arista-conexas, que por sí mismas no están conectadas.

Al agregar la siguiente arista $(a, b)$ pueden ocurrir tres situaciones:

• Ambos vértices $a$ y $b$ están en la misma componente 2-arista-conexa: entonces esta arista no es un puente, y no cambia nada en la estructura del bosque, así que podemos simplemente saltar esta arista.

  Así, en este caso el número de puentes no cambia.

• Los vértices $a$ y $b$ están en componentes conexas completamente distintas, es decir, cada uno es parte de un árbol diferente. En este caso, la arista $(a, b)$ se convierte en un puente nuevo, y estos dos árboles se combinan en uno (y todos los puentes viejos se mantienen).

  Así, en este caso el número de puentes aumenta en uno.

• Los vértices $a$ y $b$ están en una misma componente conexa, pero en distintas componentes 2-arista-conexas. En este caso, esta arista forma un ciclo junto con algunos de los puentes viejos. Todos estos puentes dejan de ser puentes, y el ciclo resultante debe comprimirse en una componente 2-arista-conexa nueva.

  Así, en este caso el número de puentes disminuye en uno o más.

En consecuencia, toda la tarea se reduce a la implementación efectiva de todas estas operaciones sobre el bosque de componentes 2-arista-conexas.

Estructuras de datos para guardar el bosque

La única estructura de datos que necesitamos es Union-Find / conjuntos disjuntos (DSU). De hecho haremos dos copias de esta estructura: una será para mantener las componentes conexas, la otra para mantener las componentes 2-arista-conexas. Y además guardamos la estructura de los árboles en el bosque de componentes 2-arista-conexas vía punteros: Cada componente 2-arista-conexa guardará el índice par[] de su ancestro en el árbol.

Ahora desarmaremos de forma consistente cada operación que necesitamos aprender a implementar:

• Comprobar si los dos vértices yacen en la misma componente conexa / 2-arista-conexa. Se hace con el algoritmo usual de DSU: solo encontramos y comparamos los representantes de los DSU.

• Unir dos árboles por alguna arista $(a, b)$. Como podría resultar que ni el vértice $a$ ni el vértice $b$ sean las raíces de sus árboles, la única forma de conectar estos dos árboles es re-enraizar uno de ellos. Por ejemplo, se puede re-enraizar el árbol del vértice $a$, y luego adjuntarlo al otro árbol poniendo el ancestro de $a$ en $b$.

  Sin embargo surge la pregunta sobre la efectividad de la operación de re-enraizar: para re-enraizar el árbol con raíz $r$ al vértice $v$, es necesario visitar todos los vértices en el camino entre $v$ y $r$ y redirigir los punteros par[] en la dirección opuesta, y también cambiar las referencias a los ancestros en el DSU que es responsable de las componentes conexas.

  Así, el costo de re-enraizar es $O(h)$, donde $h$ es la altura del árbol. Se puede hacer una estimación aún peor diciendo que el costo es $O(\text{size})$ donde $\text{size}$ es el número de vértices del árbol. La complejidad final no diferirá.

  Ahora aplicamos una técnica estándar: re-enraizamos el árbol que contiene menos vértices. Entonces es intuitivamente claro que el peor caso es cuando se combinan dos árboles de tamaños aproximadamente iguales, pero entonces el resultado es un árbol del doble de tamaño. Esto no permite que esta situación ocurra muchas veces.

  En general el costo total se puede escribir en forma de una recurrencia:

  $$T(n) = \max_{k = 1 \ldots n-1} \left{ T(k) + T(n - k) + O(\min(k, n - k))\right}$$

  $T(n)$ es el número de operaciones necesarias para obtener un árbol con $n$ vértices mediante re-enraizar y unificar árboles. Un árbol de tamaño $n$ se puede crear combinando dos árboles más pequeños de tamaño $k$ y $n - k$. Esta recurrencia tiene la solución $T(n) = O (n \log n)$.

  Así, el tiempo total gastado en todas las operaciones de re-enraizar será $O(n \log n)$ si siempre re-enraizamos el menor de los dos árboles.

  Tendremos que mantener el tamaño de cada componente conexa, pero la estructura de datos DSU lo hace posible sin dificultad.

• Buscar el ciclo formado al agregar una arista nueva $(a, b)$. Como $a$ y $b$ ya están conectados en el árbol, hay que encontrar el ancestro común más bajo (LCA) de los vértices $a$ y $b$. El ciclo consistirá de los caminos de $b$ al LCA, del LCA a $a$ y la arista $a$ a $b$.

  Después de encontrar el ciclo comprimimos todos los vértices del ciclo detectado en un solo vértice. Esto significa que ya tenemos una complejidad proporcional a la longitud del ciclo, lo que significa que también podemos usar cualquier algoritmo de LCA proporcional a la longitud, y no tenemos que usar uno rápido.

  Como toda la información sobre la estructura del árbol está disponible en el arreglo de ancestros par[], el único algoritmo de LCA razonable es el siguiente: marcar los vértices $a$ y $b$ como visitados, luego ir a sus ancestros par[a] y par[b] y marcarlos, luego avanzar a sus ancestros y así sucesivamente, hasta que lleguemos a un vértice ya marcado. Este vértice es el LCA que buscamos, y podemos encontrar los vértices del ciclo recorriendo otra vez el camino de $a$ y $b$ al LCA.

  Es obvio que la complejidad de este algoritmo es proporcional a la longitud del ciclo deseado.

• Compresión del ciclo al agregar una arista nueva $(a, b)$ en un árbol.

  Necesitamos crear una componente 2-arista-conexa nueva, que consistirá de todos los vértices del ciclo detectado (también el ciclo detectado mismo podría consistir de algunas componentes 2-arista-conexas, pero esto no cambia nada). Además es necesario comprimirlos de tal forma que la estructura del árbol no se vea alterada, y todos los punteros par[] y los dos DSU sigan siendo correctos.

  La forma más fácil de lograr esto es comprimir todos los vértices del ciclo a su LCA. De hecho el LCA es el más alto de los vértices, es decir, su puntero de ancestro par[] permanece sin cambios. Para todos los demás vértices del ciclo los ancestros no necesitan actualizarse, ya que estos vértices simplemente dejan de existir. Pero en el DSU de las componentes 2-arista-conexas todos estos vértices simplemente apuntarán al LCA.

  Implementaremos el DSU de las componentes 2-arista-conexas sin la optimización de unión por rango, por lo tanto obtendremos la complejidad $O(\log n)$ en promedio por consulta. Para alcanzar la complejidad $O(1)$ en promedio por consulta, hay que combinar los vértices del ciclo según unión por rango, y luego asignar par[] en consecuencia.

Implementación

Aquí está la implementación final de todo el algoritmo.

Como se mencionó antes, por simplicidad el DSU de las componentes 2-arista-conexas está escrito sin unión por rango, por lo tanto la complejidad resultante será $O(\log n)$ en promedio.

También en esta implementación los puentes mismos no se guardan, solo su conteo bridges. Sin embargo no será difícil crear un set de todos los puentes.

Inicialmente se llama a la función init(), que inicializa los dos DSU (creando un conjunto separado para cada vértice, y poniendo el tamaño igual a uno), y asigna los ancestros par.

La función principal es add_edge(a, b), que procesa y agrega una arista nueva.

vector<int> par, dsu_2ecc, dsu_cc, dsu_cc_size;
int bridges;
int lca_iteration;
vector<int> last_visit;
 
void init(int n) {
    par.resize(n);
    dsu_2ecc.resize(n);
    dsu_cc.resize(n);
    dsu_cc_size.resize(n);
    lca_iteration = 0;
    last_visit.assign(n, 0);
    for (int i=0; i<n; ++i) {
        dsu_2ecc[i] = i;
        dsu_cc[i] = i;
        dsu_cc_size[i] = 1;
        par[i] = -1;
    }
    bridges = 0;
}
 
int find_2ecc(int v) {
    if (v == -1)
        return -1;
    return dsu_2ecc[v] == v ? v : dsu_2ecc[v] = find_2ecc(dsu_2ecc[v]);
}
 
int find_cc(int v) {
    v = find_2ecc(v);
    return dsu_cc[v] == v ? v : dsu_cc[v] = find_cc(dsu_cc[v]);
}
 
void make_root(int v) {
    int root = v;
    int child = -1;
    while (v != -1) {
        int p = find_2ecc(par[v]);
        par[v] = child;
        dsu_cc[v] = root;
        child = v;
        v = p;
    }
    dsu_cc_size[root] = dsu_cc_size[child];
}
 
void merge_path (int a, int b) {
    ++lca_iteration;
    vector<int> path_a, path_b;
    int lca = -1;
    while (lca == -1) {
        if (a != -1) {
            a = find_2ecc(a);
            path_a.push_back(a);
            if (last_visit[a] == lca_iteration){
                lca = a;
                break;
                }
            last_visit[a] = lca_iteration;
            a = par[a];
        }
        if (b != -1) {
            b = find_2ecc(b);
            path_b.push_back(b);
            if (last_visit[b] == lca_iteration){
                lca = b;
                break;
                }
            last_visit[b] = lca_iteration;
            b = par[b];
        }
        
    }
 
    for (int v : path_a) {
        dsu_2ecc[v] = lca;
        if (v == lca)
            break;
        --bridges;
    }
    for (int v : path_b) {
        dsu_2ecc[v] = lca;
        if (v == lca)
            break;
        --bridges;
    }
}
 
void add_edge(int a, int b) {
    a = find_2ecc(a);
    b = find_2ecc(b);
    if (a == b)
        return;
 
    int ca = find_cc(a);
    int cb = find_cc(b);
 
    if (ca != cb) {
        ++bridges;
        if (dsu_cc_size[ca] > dsu_cc_size[cb]) {
            swap(a, b);
            swap(ca, cb);
        }
        make_root(a);
        par[a] = dsu_cc[a] = b;
        dsu_cc_size[cb] += dsu_cc_size[a];
    } else {
        merge_path(a, b);
    }
}

El DSU de las componentes 2-arista-conexas se guarda en el vector dsu_2ecc, y la función que devuelve el representante es find_2ecc(v). Esta función se usa muchas veces en el resto del código, ya que después de comprimir varios vértices en uno todos estos vértices dejan de existir, y en su lugar solo el líder tiene el ancestro correcto par en el bosque de componentes 2-arista-conexas.

El DSU de las componentes conexas se guarda en el vector dsu_cc, y también hay un vector adicional dsu_cc_size para guardar los tamaños de las componentes. La función find_cc(v) devuelve el líder de la componente conexa (que de hecho es la raíz del árbol).

El re-enraizado de un árbol make_root(v) funciona como se describió arriba: recorre desde el vértice $v$ vía los ancestros hasta el vértice raíz, cada vez redirigiendo el ancestro par en la dirección opuesta. El enlace al representante de la componente conexa dsu_cc también se actualiza, de modo que apunte al vértice raíz nuevo. Después de re-enraizar tenemos que asignar a la raíz nueva el tamaño correcto de la componente conexa. También hay que tener cuidado de llamar a find_2ecc() para obtener los representantes de la componente 2-arista-conexa, y no algún otro vértice que ya haya sido comprimido.

La función de búsqueda y compresión de ciclo merge_path(a, b) también está implementada como se describió arriba. Busca el LCA de $a$ y $b$ subiendo estos nodos en paralelo, hasta que encontramos un vértice por segunda vez. Por eficiencia elegimos un identificador único para cada llamada de búsqueda de LCA, y marcamos los vértices recorridos con él. Esto funciona en $O(1)$, mientras que otros enfoques como usar $set$ rinden peor. Los caminos recorridos se guardan en los vectores path_a y path_b, y los usamos para recorrerlos una segunda vez hasta el LCA, obteniendo así todos los vértices del ciclo. Todos los vértices del ciclo se comprimen adjuntándolos al LCA, de modo que la complejidad promedio es $O(\log n)$ (ya que no usamos unión por rango). Todas las aristas que pasamos han sido puentes, así que restamos 1 por cada arista del ciclo.

Finalmente la función de consulta add_edge(a, b) determina las componentes conexas en las que yacen los vértices $a$ y $b$. Si yacen en componentes conexas distintas, entonces se re-enraiza un árbol más pequeño y luego se adjunta al árbol más grande. En caso contrario, si los vértices $a$ y $b$ yacen en un mismo árbol, pero en distintas componentes 2-arista-conexas, entonces se llama a la función merge_path(a, b), que detectará el ciclo y lo comprimirá en una componente 2-arista-conexa.