Grafos 04 - LCA (Menor Ancestral Comum)

"Pedro e Paulo resolveram complicar um pouco o tradicional Jogo da Memória, em que os jogadores precisam virar duas cartas iguais. Eles colocam as cartas no chão, viradas para baixo, e fazem algumas linhas ligando pares de cartas, usando giz, de modo que para qualquer par de cartas (A, B) existe uma e apenas uma sequência de cartas distintas que leva de A até B através das linhas que eles desenharam. Com isso, ao virar duas cartas, o jogador ganha uma quantidade de pontos igual ao tamanho da sequência de linhas entre as duas cartas, se elas forem iguais. Se forem diferentes, o jogador perde aquela quantidade de pontos.

Pedro e Paulo, agora, estão estudando qual é a melhor estratégia para esse jogo e precisam da sua ajuda para resolver uma tarefa específica: dadas as ligações entre as N cartas, calcular a soma dos tamanhos das sequências entre todos os N/2 pares de cartas iguais!"

(Jogo da Memória, OBI 2014)

Antes de resolver esse problema, vamos resolver um outro:

Dada uma árvore enraizada $T$ e dois nós $x$ e $y$, ache o nó que é ancestral comum de $x$ e de $y$ e está o mais longe possível da raiz.

Olhe um exemplo onde $x = 9$ e $y = 11$ e a árvore está enraizada em $1$:

Vemos que o vértice desejado, o Menor Ancestral Comum, é o vértice $3$.

Primeiro, vamos definir, para cade vértice, seu nível de profundidade, que basicamente será igual a sua distância até a raiz. Definiremos também o pai de um vértice, que é o vértice adjacente a ele que possui um nível menor. Ficando assim:

Primeiro, temos que descobrir, para cada vértice, seu nível e seu pai. Para isso, faremos uma DFS:

Ok, agora temos o nível e o pai de cada vértice. Tendo apenas essas informações, já é possível descobrir o LCA de dois vértices (de uma maneira lenta, mas dá). Olhe para o seguinte pseudo-código:

É fácil de entender porque que o algoritmo funciona. Vamos tentar agora melhorar isso para um algoritmo $O(N \ lg N)$. Para isso, usaremos um pouco de programação dinâmica. De início, calcularemos uma tabela $ancestral$ onde $ancestral[i][j]$ representará o $2^j$-ésimo ancestral de $i$. Para calcular essa tabela, note que:

• $ancestral[i][0] = pai[i]$
• $ancestral[i][j] = ancestral[ \ ancestral[i][j-1] \ ][j-1]$, para $j > 0$.

Para montar essa tabela, o código, em C++, fica assim:

Vamos tentar, com isso, calcular $LCA(u, \ v)$. Note que, se $nivel[u] = nivel[v]$, podemos achar o LCA deles fazendo uma busca-binária: se $ancestral[u][j]$ é diferente de $ancestral[v][j]$, o LCA deles está acima desses dois, caso sejam iguais, é o contrário. Suponha então que $nivel[u] > nivel[q]$, ou seja, $u$ está mais abaixo na árvore. Nesse caso, podemos subir (no máximo $lg$ passos) para fazer com que $nivel[u] = nivel[q]$. O código, em C++, fica assim:

O algoritmo para achar o LCA de dois vértices está completo!

Apesar de sabermos achar o LCA de dois vértices, ainda não ficou claro como se aplicar esse tipo de algoritmo. Vamos então continuar a resolução do Jogo da Memória.

Se montarmos o grafo das cartas, vemos que o grafo tem que ser uma árvore. Podemos enraizar a árvore num vértice qualquer (vamos enraizar no vértice $1$, por simplicidade). Então, na seguinte figura, vamos ver como podemos calcular a distância do vértice $9$ ao vértice $11$.

Podemos observar duas coisas:

• se $x$ é um ancestral de $u$, então a distância $x \rightarrow u$ é igual a $nivel[u] - nivel[x]$.
• a distância de $u$ a $v$ equivale a soma das distância $u \rightarrow LCA(u, \ v)$ e $LCA(u, \ v) \rightarrow v$.

Então, se quisermos a distância de $u$ a $v$, sabemos que:

• $u \rightarrow LCA(u, \ v) = nivel[u] - nivel[LCA(u, \ v)]$
• $LCA(u, \ v) \rightarrow v= nivel[v] - nivel[LCA(u, \ v)]$

Portanto, a distância dos vértice $u$ ao vértice $v$ é

$$nivel[u] + nivel[v] - 2 \times nivel[LCA(u, \ v)]$$

e é isso que usaremos para resolver o problema.

Então, o código do Jogo da Memória fica assim:

Tente, agora, resolver os problemas abaixo para colocar em prática seus conhecimentos. Caso tenha dificuldade em algum problema ou alguma dúvida sobre a teoria apresentada, volte para a página inicial do curso para preencher o formulário e nos enviar sua dúvida!

Problema 1 - Colônia de Formigas

Problema 2 - LCA

Problema 3 - Query on a Tree II

Problema 4 - Distance in the Tree

As aulas do Curso Noic de Informática são propriedade do Noic e qualquer reprodução sem autorização prévia é terminantemente proibida. Se você tem interesse em reproduzir algum material do Curso Noic de Informática para poder ministrar aulas, você pode nos contatar por esta seção de contato para que possamos fornecer materiais específicos para reprodução.