Package com.jgalgo.alg.tree

Class LowestCommonAncestorOfflineUnionFind

  • All Implemented Interfaces:
    LowestCommonAncestorOffline
    public class LowestCommonAncestorOfflineUnionFind
extends LowestCommonAncestorOfflineAbstract
    Offline LCA algorithm based on Union-Find data structure.

    Given a tree and a set of pairs of vertices, the algorithm computes the lowest common ancestor of each pair. It traverse the graph by recursively on each sub tree, from the bottom up. For a node \(u\) currently processed, it calls the recursive function on each of its child \(v\) sequentially, and union \(u\) with \(v\), until all the subtree of \(u\) is a single set in the union-find data structure. Then, for each query \((u, w)\), if \(w\) was already processed, the LCA is the root of the set containing \(w\).

    The algorithm uses linear space and runs in \(O(n + q) \alpha (n + q)\) time, where \(n\) is the number of vertices in the tree, \(q\) is the number of queries, and \(\alpha\) is the inverse Ackermann function.

    Based on 'Applications of Path Compression on Balanced Trees' by Tarjan (1979).

    Author:
    Barak Ugav