lowest_common_ancestor.cpp File Reference

Data structure for finding the lowest common ancestor of two vertices in a rooted tree using binary lifting. More...

#include <cassert>
#include <iostream>
#include <queue>
#include <utility>
#include <vector>

Include dependency graph for lowest_common_ancestor.cpp:

Go to the source code of this file.

Classes
class	graph::Graph< T >
class	graph::RootedTree
class	graph::LowestCommonAncestor

Namespaces
namespace	graph
	Graph Algorithms.

Functions
static void	tests ()
int	main ()

Detailed Description

Data structure for finding the lowest common ancestor of two vertices in a rooted tree using binary lifting.

Algorithm: https://cp-algorithms.com/graph/lca_binary_lifting.html

Complexity:

• Precomputation: \(O(N \log N)\) where \(N\) is the number of vertices in the tree
• Query: \(O(\log N)\)
• Space: \(O(N \log N)\)

Example:
Tree:

            _  3  _
         /     |     \
       1       6       4
     / |     /   \       \
   7   5   2       8       0
           |
           9

lowest_common_ancestor(7, 4) = 3
lowest_common_ancestor(9, 6) = 6
lowest_common_ancestor(0, 0) = 0
lowest_common_ancestor(8, 2) = 6

The query is symmetrical, therefore lowest_common_ancestor(x, y) = lowest_common_ancestor(y, x)

Definition in file lowest_common_ancestor.cpp.

Function Documentation

main()

int main

(

void

)

Main function

Definition at line 255 of file lowest_common_ancestor.cpp.

           {
    tests();
    return 0;
}

tests()

static void tests ( )

static

Unit tests

Returns

none

     _  3  _
  /     |     \
1       6       4

/ | / \ \ 7 5 2 8 0 | 9

Definition at line 234 of file lowest_common_ancestor.cpp.

                    {
    std::vector<std::pair<int, int> > edges = {
        {7, 1}, {1, 5}, {1, 3}, {3, 6}, {6, 2}, {2, 9}, {6, 8}, {4, 3}, {0, 4}};
    graph::RootedTree t(edges, 3);
    graph::LowestCommonAncestor lca(t);
    assert(lca.lowest_common_ancestor(7, 4) == 3);
    assert(lca.lowest_common_ancestor(9, 6) == 6);
    assert(lca.lowest_common_ancestor(0, 0) == 0);
    assert(lca.lowest_common_ancestor(8, 2) == 6);
}