Ancestro común más bajo - algoritmo offline de Tarjan

Tenemos un árbol $G$ con $n$ nodos y tenemos $m$ consultas de la forma $(u, v)$ . Para cada consulta $(u, v)$ queremos encontrar el ancestro común más bajo (LCA) de los vértices $u$ y $v$ , es decir, el nodo que es ancestro de $u$ y de $v$ y tiene la mayor profundidad en el árbol. El nodo $v$ también es un ancestro de $v$ , así que el LCA también puede ser uno de los dos nodos.

En este artículo resolveremos el problema de forma offline, es decir, asumimos que todas las consultas se conocen de antemano, y por tanto respondemos las consultas en el orden que queramos. El siguiente algoritmo permite responder las $m$ consultas en tiempo total $O(n + m)$ , es decir, para $m$ suficientemente grande en $O(1)$ por cada consulta.

Algoritmo

El algoritmo lleva el nombre de Robert Tarjan, que lo descubrió en 1979 y también hizo muchas otras contribuciones a la estructura de datos Union-Find / conjuntos disjuntos (DSU), que se usará intensamente en este algoritmo.

El algoritmo responde todas las consultas con un solo recorrido DFS del árbol. A saber, una consulta $(u, v)$ se responde en el nodo $u$ , si el nodo $v$ ya ha sido visitado previamente, o viceversa.

Así que supongamos que estamos actualmente en el nodo $v$ , ya hemos hecho las llamadas recursivas de DFS, y también ya visitamos el segundo nodo $u$ de la consulta $(u, v)$ . Aprendamos cómo encontrar el LCA de estos dos nodos.

Nótese que $\text{LCA}(u, v)$ es o el nodo $v$ o uno de sus ancestros. Así que hay que encontrar el nodo más bajo entre los ancestros de $v$ (incluyendo $v$ ), para el cual el nodo $u$ es un descendiente. También nótese que para un $v$ fijo los nodos visitados del árbol se parten en un conjunto de conjuntos disjuntos. Cada ancestro $p$ del nodo $v$ tiene su propio conjunto que contiene este nodo y todos los subárboles con raíces en aquellos de sus hijos que no son parte del camino de $v$ a la raíz del árbol. El conjunto que contiene el nodo $u$ determina el $\text{LCA}(u, v)$ : el LCA es el representante del conjunto, a saber el nodo que yace en el camino entre $v$ y la raíz del árbol.

Solo hay que aprender a mantener de forma eficiente todos estos conjuntos. Para este propósito aplicamos la estructura de datos DSU. Para poder aplicar unión por rango, guardamos el representante real (el valor en el camino entre $v$ y la raíz del árbol) de cada conjunto en el arreglo ancestor.

Discutamos la implementación del DFS. Supongamos que estamos visitando actualmente el nodo $v$ . Colocamos el nodo en un conjunto nuevo en el DSU, ancestor[v] = v. Como es usual procesamos todos los hijos de $v$

Finalmente, después de procesar todos los hijos podemos responder todas las consultas de la forma $(u, v)$ para las que $u$ ya ha sido visitado. La respuesta a la consulta, es decir, el LCA de $u$ y $v$ , será el nodo ancestor[find_set(u)]. Es fácil ver que una consulta solo se responderá una vez.

Determinemos la complejidad temporal de este algoritmo. Primero tenemos $O(n)$ por el DFS. Segundo tenemos las llamadas a la función union_sets que ocurren $n$ veces, resultando también en $O(n)$ . Y tercero tenemos las llamadas a find_set por cada consulta, lo que da $O(m)$ . Así que en total la complejidad temporal es $O(n + m)$ , lo que significa que para $m$ suficientemente grande esto corresponde a $O(1)$ para responder una consulta.

Implementación

Aquí hay una implementación de este algoritmo. La implementación del DSU no se ha incluido, ya que se puede usar sin ninguna modificación.


vector<vector<int>> adj;
vector<vector<int>> queries;
vector<int> ancestor;
vector<bool> visited;
 
void dfs(int v)
{
    visited[v] = true;
    ancestor[v] = v;
    for (int u : adj[v]) {
        if (!visited[u]) {
            dfs(u);
            union_sets(v, u);
            ancestor[find_set(v)] = v;
        }
    }
    for (int other_node : queries[v]) {
        if (visited[other_node])
            cout << "LCA of " << v << " and " << other_node
                 << " is " << ancestor[find_set(other_node)] << ".\n";
    }
}
 
void compute_LCAs() {
    // initialize n, adj and DSU
    // for (each query (u, v)) {
    //    queries[u].push_back(v);
    //    queries[v].push_back(u);
    // }
 
    ancestor.resize(n);
    visited.assign(n, false);
    dfs(0);
}