Menor Ancestral Comum: algoritmo de Tarjan

Temos uma árvore $G$ com $n$ nós e temos $m$ consultas $(u, v)$. Para cada consulta $(u, v)$ queremos encontrar o menor ancestral comum dos vértices $u$ e $v$.

Neste artigo, resolveremos o problema off-line, ou seja, assumimos que todas as consultas são conhecidas antecipadamente e, portanto, respondemos às consultas na ordem que desejar. O algoritmo a seguir permite responder a todas as $m$ consultas em $O(n + m)$, ou seja, para um $m$ suficientemente grande em $O(1)$ por cada consulta.

Algoritmo

O algoritmo recebeu o nome de Robert Tarjan, que o descobriu em 1979 e também fez muitas outras contribuições para a estrutura de dados: Disjoint Set Union, que será muito usada nesse algoritmo.

O algoritmo responde a todas as consultas com uma travessia da DFS da árvore. Ou seja, uma consulta $(u, v)$ é respondida no nó $u$, se o nó $v$ já tiver sido visitado anteriormente ou vice-versa.

Então, vamos supor que estamos atualmente no nó $v$, já fizemos chamadas recursivas da DFS e também já visitamos o segundo nó $u$ da consulta $(u, v)$. Vamos aprender como encontrar o LCA desses dois nós.

Observe que $\text{LCA}(u, v)$ é o nó $v$ ou um de seus ancestrais. Portanto, precisamos encontrar o nó mais baixo entre os ancestrais de $v$ (incluindo $v$), para o qual o nó $u$ é um descendente. Observe também que, para um $v$ fixo os nós visitados da árvore se dividem em um conjunto de conjuntos disjuntos(disjoint sets). Cada ancestral $p$ do nó $v$ possui seu próprio conjunto contendo esse nó e todas as subárvores com raízes nos filhos que não fazem parte do caminho entre $v$ e a raiz da árvore. O conjunto que contém o nó $u$ determina o $\text{LCA}(u, v)$: o LCA é o representante do conjunto, ou seja, o nó que fica no caminho entre $v$ e a raiz do árvore.

Só precisamos aprender a manter com eficiência todos esses conjuntos. Para esse fim, aplicamos a estrutura de dados DSU. Para poder aplicar Union by Rank, armazenamos o representante real (o valor no caminho entre $v$ e a raiz da árvore) de cada conjunto na array ancestor.

Vamos discutir a implementação do DFS. Vamos supor que estamos atualmente visitando o nó $v$. Colocamos o nó em um novo conjunto no DSU, ancestor[v] = v. Como sempre, processamos todos os filhos de $v$. Para isso, primeiro devemos chamar recursivamente a DFS nesse nó e, em seguida, adicionar esse nó com toda a sua subárvore ao conjunto de $v$. Isso pode ser feito com a função union_sets e a seguinte definição: ancestor[find_set(v)] = v (isso é necessário, porque union_sets pode alterar o representante do conjunto).

Finalmente, depois de processar todos os filhos, podemos responder a todas as consultas da forma $(u, v)$, em que $u$ já foi visitado. A resposta para a consulta, ou seja, o LCA de $u$ e $v$, será o nó ancestor[find_set(u)]. Uma consulta será respondida apenas uma vez.

Vamos determinar a complexidade do tempo desse algoritmo. Em primeiro lugar, temos $O(n)$ por causa da DFS. Em segundo lugar, temos as chamadas da função union_sets que acontece $n$ vezes, resultando também em $O(n)$. E em terceiro lugar, temos as chamadas de find_set para cada consulta, o que nos dá $O(m)$. Portanto, no total, a complexidade do tempo é $O(n + m)$, o que significa que, para $m$'s suficientemente grandes, isso corresponde a $O(1)$ para responder a uma consulta.

Implementação

Aqui está uma implementação desse algoritmo. A implementação do DSU não foi incluída, pois pode ser usada sem modificações.

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 de " << v << " e " << other_node
                 << " : " << ancestor[find_set(other_node)] << ".\n";
    }
}

void compute_LCAs() {
    // inicializa n, adj e DSU
    // for (cada query (u, v)) {
    //    queries[u].push_back(v);
    //    queries[v].push_back(u);
    // }

    ancestor.resize(n);
    visited.assign(n, false);
    dfs(0);
}