Muestra las diferencias entre dos versiones de la página.
Ambos lados, revisión anterior Revisión previa Próxima revisión | Revisión previa Última revisión Ambos lados, revisión siguiente | ||
algoritmos-oia:grafos:arboles:lowest-common-ancestor [2017/12/26 19:13] sebach ↷ Page moved from algoritmos-oia:lowest-common-ancestor to algoritmos-oia:grafos:arboles:lowest-common-ancestor |
algoritmos-oia:grafos:arboles:lowest-common-ancestor [2017/12/30 10:27] sebach [Código] |
||
---|---|---|---|
Línea 1: | Línea 1: | ||
===== Ancestro común más bajo ===== | ===== 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. | 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 ===== | ===== Código ===== | ||
- | CODIGO! | + | <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 ==== | ==== Complejidad ==== | ||