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