lcaBinaryLifting
lcaBinaryLifting(adj: usize[][], root: usize): Lca construye tablas de binary lifting sobre el árbol no dirigido descrito por la lista de adyacencia adj, donde adj[v] guarda los vecinos del vértice v y root ancla cada consulta. La Lca devuelta es un handle de propiedad del llamador de tyrus:algorithm; expone query(u, v), que devuelve el menor ancestro común de los vértices u y v en O(log n) con binary lifting.
Construcción
| Sintaxis | Descripción |
|---|---|
lcaBinaryLifting(adj: usize[][], root: usize) | Construir tablas de LCA sobre el árbol adj, enraizado en root |
Métodos
| Método | Firma | Devuelve | Descripción |
|---|---|---|---|
query | (u: usize, v: usize) | usize | Menor ancestro común de los vértices u y v |
Complejidad
| Operación | Complejidad Temporal |
|---|---|
| construcción | O(n log n), tablas de binary lifting |
query | O(log n) |
| memoria | O(n log n) |
Ejemplos
árbol balanceado
tyrus
import { lcaBinaryLifting } from "tyrus:algorithm";
const adj: usize[][] = [[1, 2], [0, 3, 4], [0, 5, 6], [1], [1], [2], [2]];
const lca = lcaBinaryLifting(adj, 0);
print(lca.query(3, 4)); // 1
print(lca.query(5, 6)); // 2
print(lca.query(3, 6)); // 0camino profundo
tyrus
import { lcaBinaryLifting } from "tyrus:algorithm";
const path: usize[][] = [[1], [0, 2], [1, 3], [2, 4], [3, 5], [4, 6], [5, 7], [6, 8], [7, 9], [8]];
const lca = lcaBinaryLifting(path, 0);
print(lca.query(9, 1)); // 1
print(lca.query(9, 8)); // 8
print(lca.query(0, 9)); // 0único vértice
tyrus
import { lcaBinaryLifting } from "tyrus:algorithm";
const single: usize[][] = [[]];
const lca = lcaBinaryLifting(single, 0);
print(lca.query(0, 0)); // 0importación por namespace
tyrus
import * as alg from "tyrus:algorithm";
const lca = alg.lcaBinaryLifting([[1], [0, 2], [1]], 0);
print(lca.query(1, 2)); // 1
print(lca.query(0, 2)); // 0