Herramientas de usuario
algoritmos-oia:grafos:arboles:lowest-common-ancestor
Diferencias
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 | ||
|
algoritmos-oia:grafos:arboles:lowest-common-ancestor [2017/12/26 19:13] sebach ↷ Links adapted because of a move operation |
algoritmos-oia:grafos:arboles:lowest-common-ancestor [2017/12/30 10:29] (actual) sebach [Código] |
||
|---|---|---|---|
| Línea 37: | Línea 37: | ||
| ===== Código ===== | ===== 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 ==== | ==== Complejidad ==== | ||
algoritmos-oia/grafos/arboles/lowest-common-ancestor.1514315626.txt.gz · Última modificación: 2017/12/26 19:13 por sebach
Herramientas de la página
Excepto donde se indique lo contrario, el contenido de este wiki esta bajo la siguiente licencia: Public Domain
