Package com.jgalgo.alg.tree

Class LowestCommonAncestorOfflineUnionFind

java.lang.Object

com.jgalgo.alg.tree.LowestCommonAncestorOfflineAbstract

com.jgalgo.alg.tree.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

Nested Class Summary

Nested classes/interfaces inherited from interface com.jgalgo.alg.tree.LowestCommonAncestorOffline

LowestCommonAncestorOffline.IQueries, LowestCommonAncestorOffline.IResult, LowestCommonAncestorOffline.Queries<V,E>, LowestCommonAncestorOffline.Result<V,E>

Constructor Summary

Constructors

Constructor	Description
LowestCommonAncestorOfflineUnionFind()	Create a new offline LCA algorithm object.

Method Summary

Methods inherited from class com.jgalgo.alg.tree.LowestCommonAncestorOfflineAbstract

findLowestCommonAncestors

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

LowestCommonAncestorOfflineUnionFind

public LowestCommonAncestorOfflineUnionFind()

Create a new offline LCA algorithm object.

Please prefer using LowestCommonAncestorOffline.newInstance() to get a default implementation for the LowestCommonAncestorOffline interface.