Diferencias

Muestra las diferencias entre dos versiones de la página.

--- algoritmos-oia:grafos:arboles:lowest-common-ancestor [2017/12/24 10:09]
sebach [Múltiples queries]
+++ algoritmos-oia:grafos:arboles:lowest-common-ancestor [2017/12/30 10:29] (actual)
sebach [Código]
@@ Línea 1: / Línea 1: @@
 ===== Ancestro común más bajo =====
-Como mencionamos [[algoritmos-oia/arboles|acá]], el ancestro común más bajo ("lowest common ancestor" en inglés, abreviado LCA) de dos nodos es un nodo, que contiene en su subárbol a ambos nodos dados, y que de todos los que cumplen eso, es el más bajo.
+Como mencionamos [[algoritmos-oia:grafos:arboles|acá]], el ancestro común más bajo ("lowest common ancestor" en inglés, abreviado LCA) de dos nodos es un nodo, que contiene en su subárbol a ambos nodos dados, y que de todos los que cumplen eso, es el más bajo.
 Esto puede ser interesante por ejemplo para conocer el camino (único) entre dos nodos. El camino será ir subiendo desde uno de ellos, yendo a su padre, al padre de su padre, y así hasta llegar al LCA de los nodos, y desde ahí empezar a bajar a través de todos ancestros del segundo nodo, hasta llegar a él.
@@ Línea 37: / Línea 37: @@
 ===== Código =====
-CODIGO!
+Dejo el código para un árbol binario formado en el main, cada nodo tiene dos hijos, la raíz la coloco en el $0$, y voy calculando los padres adyacentes a cada nodo en la función rootTree recursiva.
+Los hijos de cada nodo $i$ son $2*i+1$ y $2*i+2$, hasta que me paso del $N$ ingresado al principio.
+<code cpp lca.cpp>
+#include<bits/stdc++.h>
+using namespace std;
+#define forn(i,n) for(int i=0; i<(int)(n); i++)
+#define pb push_back
+const int maxn=100005;
+const int maxlogn=20;
+vector<int> level(maxn, -1);
+vector< vector<int> > parent(maxn, vector<int>(maxlogn, -1));
+vector< vector<int> > grafo;
+void rootTree(int toy, int vengo, int nivel){
+ level[toy]=nivel;
+ parent[toy][0]=vengo;
+ forn(i, grafo[toy].size()){
+ if(grafo[toy][i]==vengo)continue;
+ rootTree(grafo[toy][i], toy, nivel+1);
+ }
+}
+int LCA(int u, int v){
+ if(level[u]<level[v]){
+ int tmp=u;
+ u=v;
+ v=tmp;
+ }
+ //cout<<"nodo mas abajo "<<u<<endl;
+ int log=0;
+ while( (1<<log)<=level[u])log++;
+ log--;
+ //cout<<"LOG = "<<log<<endl;
+ for(int i=log; i>=0; i--){
+ if(level[u]-(1<<i) >=level[v]){
+ //cout<<"subo de "<<u<<" a ";
+ u=parent[u][i];
+ //cout<<u<<endl;
+ }
+ }
+ //cout<<"mismo nivel "<<u<<" y "<<v<<endl;
+ for(int i=log; i>=0; i--){
+ if(parent[u][i]!=-1 && parent[u][i]!=parent[v][i]){
+ //cout<<"subo de "<<u;
+ u=parent[u][i];
+ //cout<<" a "<<u<<" y de "<<v<<" a ";
+ v=parent[v][i];
+ //cout<<v<<endl;
+ }
+ }
+ int p;
+ if(v!=u){
+ p=parent[v][0];
+ }else{
+ p=v;
+ }
+ return p;
+}
+int main(){
+ int N;
+ cin>>N;
+ forn(i, N){
+ vector<int> v;
+ if(2*i+1<N)v.pb(2*i+1);
+ if(2*i+2<N)v.pb(2*i+2);
+ if(i>0)v.pb((i-1)/2);
+ grafo.pb(v);
+ }
+ rootTree(0, -1, 0);
+ for(int j=1; (1<<j)<N; j++){
+ forn(i, grafo.size()){
+ if(parent[i][j-1]!=-1){
+ parent[i][j]=parent[parent[i][j-1]][j-1];
+ }
+ }
+ }
+ int q;
+ cin>>q;
+ while(q--){
+ int u, v;
+ cin>>u>>v;
+ cout<<LCA(u, v)<<endl;
+ }
+}
+</code>
 ==== Complejidad ====
@@ Línea 51: / Línea 142: @@
 [[https://www.codechef.com/problems/RBTREE|Queries sobre caminos entre pares de nodos]]
 [[http://www.spoj.com/problems/QTREE2/|Queries, distancia entre nodos y k-esimo del camino]] (difícil)

OIA-Wiki

Herramientas de usuario

Herramientas del sitio

Diferencias

Herramientas de la página