Algorithms_in_C++ 1.0.0
Set of algorithms implemented in C++.
|
Public Member Functions | |
LowestCommonAncestor (const RootedTree &tree_) | |
Stores the tree and precomputs "up lifts". | |
int | lowest_common_ancestor (int u, int v) const |
Query the structure to find the lowest common ancestor. Assumes that the provided numbers are valid indices of vertices. Iterativelly modifies ("lifts") u an v until it finnds their lowest common ancestor. | |
Public Attributes | |
const RootedTree & | tree |
std::vector< std::vector< int > > | up |
for every vertex stores a list of its ancestors by powers of two For each vertex, the first element of the corresponding list contains the index of its parent. The i-th element of the list is an index of the (2^i)-th ancestor of the vertex. | |
Protected Member Functions | |
void | populate_up () |
A structure that holds a rooted tree and allow for effecient queries of the lowest common ancestor of two given vertices in the tree.
|
inlineexplicit |
Stores the tree and precomputs "up lifts".
tree_ | rooted tree. |
|
inline |
Query the structure to find the lowest common ancestor. Assumes that the provided numbers are valid indices of vertices. Iterativelly modifies ("lifts") u an v until it finnds their lowest common ancestor.
u | index of one of the queried vertex |
v | index of the other queried vertex |
|
inlineprotected |
Populate the "up" structure. See above.