LCA - "Naive" e Sparse Table

Veja mais sobre a matriz esparsa utilizada para implementar a rmq utilizada nesse algoritmo.

Veja mais sobre o problema do LCA

Introdução

O Lowest Common Ancestor (LCA) consiste em identificar o ancestral comum entre dois nós de uma árvore e que esteja o mais abaixo da árvore possível. Por exemplo, na ávore abaixo, lca(4,6)= 1. Ou seja, o nó 1 é ancestral comum entre os nós 4 e 6 com maior altura.

Mais exemplos:

lca(4,5) = 3

lca(9,3) = 0

lca(2,1) = 1

Estratégias de solução

• Busca completa.

Porém, essa solução, em uma árvore desbalanceada tem custo de O(n). Se forem muitas consultas, então ela se torna inviável.

• Redução ao problema de RMQ

Nesse caso, iremos transformar o problema do LCA em um problema de RMQ. Faremos essa redução em O(n). Depois, se os elementos do array mudam, então podemos usar uma segment tree para resolver o RMQ, caso contrário é mais eficiente utilizar uma sparse table.

Busca completa

A forma mais fácil de resolver esse problema é fazendo uma busca completa:

0. Seja u e v os nós dados

1. Percorra de u até a raiz. Guarde os nós percorridos.

2. Percorra de v até a raiz. Guarde os nós percorridos.

3. Percorra as duas listas procurando um elemento em comum.

Nessa solução, se a árvore (suponha uma árvore binária) estiver balanceada, teremos:

passo 1: log(n)

passo 2: log(n)

passo 3: log(n)

Logo, seria uma solução em 3 log(n) ou : O(log(n))

Mas é claro que se você for responder esse problema em alguma competição, é provável que existe um caso de teste em que a árvore esteja completamente desbalanceada, ela funcionará como uma lista encadeada. E portanto, as operações passam a ser:

passo 1: n

passo 2: n

passo 3: n

Logo, temos O(n)

Veja a quantidade de nós do seu problema e se for pequeno, você pode arriscar essa solução. Segue o código.

Código solução "naive"

/*

Rodrigo Paes

Lowest Common Ancestor "Naive"

*/

#include <bits/stdc++.h>

using namespace std;

typedef vector<int> vi;

#define pb push_back

vi parent;

vi u_sequence;

vi v_sequence;

/*

O(n)

Constrói a árvore de visitação dos nois nós, de baixo pra cima. Ou seja, a raiz estará

sempre na posição size()-1.

*/

void build_sequence(int u, int v)

{

    int p = parent[u];

    u_sequence.pb(u);

    while (p!=-1) {

        u_sequence.pb(p);

        p = parent[p];

    }

    p = parent[v];

    v_sequence.pb(v);

    while (p!=-1) {

        v_sequence.pb(p);

        p = parent[p];

    }

}

// O(n)

int lca(int u, int v)

{

    build_sequence(u, v);

    int diff = u_sequence.size() - v_sequence.size();

    int u_index, v_index;

    /*

    Se os tamanhos são diferentes, precisamos começar a comparar somente elementos

    da mesma altura. Logo, precisamos ignorar os elementos mais baixos do ramo

    de maior altura percorrida.

    Se o diff > 0, então u é maior. Logo, vamos ignorar essa diferença de elementos em u.

    Se diff < 0, então u é menor, e portanto, devemos começar da posição 0, pois quem

    terá elementos ignorados será o v

    */

    u_index = max(0, diff);

    /*

    Se diff > 0, então u será ignnorado e portanto devemos começar v em 0

    se diff < 0, então v terá elementos ignorados nessa quantidade. Mas perceba

    que precisaremos multiplicar por -1, pois diff é negativo.

    */

    v_index = max(0, -1* diff);

    while (u_index < u_sequence.size()  && v_index < v_sequence.size())

    {

        if (u_sequence[u_index] == v_sequence[v_index]) {

            return u_sequence[u_index];

        }

        v_index ++;

        u_index ++;

    }

    return -1;

}

int main()

{  

    int n; //vertices

    int e; // edges

    int s, t;

    int start, end;

    cin >> n >> e;

    parent.resize(n,-1);

    for (int i=0; i< e; ++i)

    {  

        cin >> s >> t;

        parent[t] = s;       

    }

    cin >> start >> end;

    cout << lca(start,end) << endl;

}

Arquivo para teste:

10

9

0 1

0 7

1 2

1 3

1 6

3 4

3 5

7 8

7 9

4 6

LCA utilizando uma matriz esparsa

A ideia aqui é enxergar o problema como um problema de RMQ.

Imagine que vamos percorrer a árvore em profundidade utilizando o DFS.

Imagine também que a cada nó visitado, nós o colocamos em uma lista. Por exemplo, na árvore a seguir, a ordem de visitação do dfs seria:

Ordem de visitação do DFS(0):

visit_sequence = [0, 1, 2, 1, 3, 4, 3, 5, 3, 1, 6, 1, 0, 7, 8, 7, 9, 7, 0]

Perceba que estamos colocando na lista o nó tanto na descida da árvore quanto também quando ele volta da recursão (na subida). Por isso, que um mesmo nó aparece várias vezes nessa lista.

Se você olhar para a árvore verá que o LCA(4, 6) é o nó 1, por exemplo.

Veja também que o LCA (4, 6) é o nó com menor altura dentre todos os nós visitados entre 4 e 6. Ao olharmos para a lista, os nós visitados entre 4 e 6 são:

visit_sequence = [0, 1, 2, 1, 3, 4, 3, 5, 3, 1, 6, 1, 0, 7, 8, 7, 9, 7, 0]

Dentre esses nós destacados, o 3 possui altura 2, o 5 altura 3, e o 1 altura 1. Logo, o nó com menor altura entre eles é o 1, que corresponde exatamente ao LCA (4, 6).

Logo, durante o dfs, além de guardar a sequência de visitação, precisamos guardar também as alturas dessas visitações. Logo, esse array (depth) ficará:

depth = [0, 1, 2, 1, 2, 3, 2, 3, 2, 1, 2, 1, 0, 1, 2, 1, 2, 1, 0]

visit_sequence = [0, 1, 2, 1, 3, 4, 3, 5, 3, 1, 6, 1, 0, 7, 8, 7, 9, 7, 0]

Como queremos encontrar o nó de menor altura do intervalo de visitação entre eles, queremos o menor valor do intervalo destacado do array depth:

índices: = 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18

depth = [0, 1, 2, 1, 2, 3, 2, 3, 2, 1, 2 , 1 , 0 , 1 , 2 , 1 , 2 , 1 , 0 ]

visit_sequence = [0, 1, 2, 1, 3, 4, 3, 5, 3, 1, 6 , 1 , 0 , 7 , 8 , 7 , 9 , 7 , 0 ]

Certo, então calculando o valor mínimo entre [2, 3, 2, 1] , é o 1. Esse elemento está situado na posição 9 do array depth:

índices: = 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18

depth = [0, 1, 2, 1, 2, 3, 2, 3, 2, 1, 2 , 1 , 0 , 1 , 2 , 1 , 2 , 1 , 0 ]

E lembre-se que obtivemos o array depth fazendo a visitação DFS, que guardamos em visit_sequence. Logo, o nó visitado nesse ponto foi o nó da posição 9 do visit_sequence, que é o 1. E assim resolvemos.

Entretanto, do jeito que fizemos, para acharmos o intervalo de visitação, tivemos que fazer isso sequencialmente:

LCA(4, 6):

1. i = procurar a posição que 4 aparece pela primeira vez em visit_sequence

2. j = procurar a posição que 6 aparece pela primeira vez em visit_sequence

3. x = índice do menor valor entre (i, j) em depth

4. resposta = visit_sequence[x]

Para evitar que os passos 1 e 2 sejam feitos sequencialmente, vamos criar um terceiro array e guardar nesse array a primeira vez que um determinado nó aparece em visit_sequence. Assim, first_ocurrence[i] significa a primeira vez que o nó i aparece em visit_sequence.

índices: = 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18

depth = [0, 1, 2, 1, 2, 3, 2, 3, 2, 1, 2 , 1 , 0 , 1 , 2 , 1 , 2 , 1 , 0 ]

visit_sequence = [0, 1, 2, 1, 3, 4, 3, 5, 3, 1, 6 , 1 , 0 , 7 , 8 , 7 , 9 , 7 , 0 ]

first_ocurrence= [0, 1, 2, 4 ...]

Percebam que a primeira vez que o nó 0 aparece em visit_sequence é na posição 0. A mesma coisa para os nós 1 e 2.

Mas perceba que o nó 3 aparece pela primeira vez somente no índice 4 de visit_sequence, por isso, first_ocurrence[3] = 4. E assim continuamos preenchendo esse array:

índices: = 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18

depth = [0, 1, 2, 1, 2, 3, 2, 3, 2, 1, 2 , 1 , 0 , 1 , 2 , 1 , 2 , 1 , 0 ]

visit_sequence = [0, 1, 2, 1, 3, 4, 3, 5, 3, 1, 6 , 1 , 0 , 7 , 8 , 7 , 9 , 7 , 0 ]

first_ocurrence= [0, 1, 2, 4, 5, 7,10,13,14,16, -1, -1, -1, -1, -1, -1, -1, -1, -1]

LCA(u,v) :

Agora o nosso algoritmo pode ser resolvido mais eficientemente:

1. i = first_ocurrence[u] // no exemplo, como u=4, então i seria 5

2. j = first_ocurrence[v] // v=6, j seria 10

3. x = índice do menor valor entre (i, j) em depth // minimo entre (5,10) em depth, nesse caso x=9

4. resposta = visit_sequence[x] // 1

O último passo é resolver o problema de achar o mínimo no intervalo (i,j) em depth. Mas esse problema nós já resolvemos com matrizes esparsas aqui.

Logo, vamos construir uma matriz esparça usando para isso o array depth. Com isso, essa operação também será feita em O(1).

Assim, todo o nosso LCA(u,v) será resolvido em O(1). Mas é obvio que temos os custos desses pré-processamentos.Sendo assim:

• Redução de LCA a RMQ: O(n)
  • Isso envolve rodar um DFS para constuir os arrays auxiliares
• Construção da matriz esparsa: O( n log(n) )
• Consulta: O(1)
• Não faremos atualização dos valores do array

Código LCA com matriz esparsa

/*

LCA com Sparse Table

Rodrigo Paes

Lowest Common Ancestor com Sparce Table

*/

#include <bits/stdc++.h>

using namespace std;

typedef vector<int> vi;

typedef vector<vi> vvi;

#define pb push_back

vvi adj_list;

vi visit_sequence; // sequência de nós visitados

/*

Altura da visitação do nó em visit_sequence. Para saber qual o nó, basta pegar o mesmo índice em ambos.

Por exemplo,

quarto nó visitado é: visit_sequence[3]

a altura da visitação foi: depth[3]

Esse nó foi visitado pela primeira vez em:

first_ocurrence[ visit_sequence[3] ]

*/

vi depth;

vi first_ocurrence; // guarda o índice da primeira ocorrência de um nó na visit_sequence

int idx;

#define N 1000 * 2 // número máximo de vértices * 2

#define M 11

int spt[N][M]; //sparse table

/*

v = vertice a ser visitado

d = depth

p = parent

*/

void dfs(int v, int d=0, int p=-1)

{

    first_ocurrence[v] = idx;

    visit_sequence[idx] = v;   

    depth[idx] = d;

    // Toda vez que uma visita é feita, incrementa o idx

    ++idx;

    for (auto& u: adj_list[v])

    {

        if (p != u) //evita ciclos, caso haja

        {

            dfs(u, d+1, v);

            visit_sequence[idx] = v;

            depth[idx] = d;

            // como tbm contamos a visita quando ele retrocede na árvore, precisamo incrementar o idx

            ++idx;

        }

    }

}

void print_all()

{

    for (auto i: first_ocurrence)

    {

        printf("%d ",i);

    }

    printf("\n");

    for (auto i: visit_sequence)

    {

        printf("%d ",i);

    }

    printf("\n");

    for (auto i: depth)

    {

        printf("%d ",i);

    }

    printf("\n");

}

// Constrói baseado na altura

void build()

{   

    int n = depth.size();

    for (int j = 0; (1 <<j) <= n; ++j)

    {       

        for (int i=0; (i + (1<< j) - 1) < n; ++i)

        {

            if (j) //se não é zero

            {               

                int pos1 = spt[i][j-1];

                int pos2 = spt[i + (1<<(j-1))][j-1];

                spt[i][j] = depth[pos1] < depth[pos2] ? pos1 : pos2;

            }

            else

            {

                spt[i][j] = i;

            }

        }

    }

}

/*

Retorna o índice do array de alturas com menor altura no intervalo

*/

int rmq(int i, int j)

{   

    int length = j-i +1;

    int k = (int) floor(log((double) length) / log(2.0));

    if (depth[spt[i][k]] <= depth[spt[j-(1<<k)+1][k]])

    {

        return spt[i][k];

    }

    else

    {

        return spt[j - (1<<k) + 1][k];

    }

}

int lca(int v, int u)

{

    if (u<v)

    {

        swap(u,v);

    }

    // descobre qual o elemento que possui a menor altura entre os nós v e u

    // e depois retorna o elemento em si

    return visit_sequence[ rmq(first_ocurrence[v],first_ocurrence[u])];

}

int main()

{   

    int n; //vertices

    int e; // edges

    int s, t;

    int start, end;

    cin >> n >> e;

    adj_list.resize(n);

    first_ocurrence.resize(n);

    visit_sequence.resize(2*n);

    depth.resize(2*n);

    idx = 0;

    for (int i=0; i< e; ++i)

    {   

        cin >> s >> t;

        adj_list[s].pb(t);

    }

    dfs(0);

    build();

    print_all();

    cin >> start >> end;

    cout << lca(start,end) << endl;

}

Arquivo para teste:

10

9

0 1

0 7

1 2

1 3

1 6

3 4

3 5

7 8

7 9

4 6