Lowest Common Ancestor with Linking

Description

Given a collection of rooted trees, answer queries of the form, "What is the nearest common ancestor of vertices $x$ and $y$?" In this version of the problem, the queries are on-line. Interspersed with the queries are on-line commands $link(x, y)$ such that $y$, but not necessarily $x$, is a tree root. The effect of a command $link(x, y)$ is to combine the trees containing $x$ and $y$ by making $x$ the parent of $y$.

Related Problems

Generalizations: Lowest Common Ancestor

Related: Off-Line Lowest Common Ancestor, Lowest Common Ancestor with Static Trees, Lowest Common Ancestor with Linking Roots, Lowest Common Ancestors with Linking and Cutting

Parameters

$n$: number of vertices

$m$: number of total number of operations (queries, links, and cuts)

Table of Algorithms

Name	Year	Time	Space	Approximation Factor	Model	Reference
Aho, Hopcroft, and Ullman (Linking)	1976	$O((m+n)$*log(n))	$O(n*log(n)$)	Exact	Deterministic	Time & Space
Modified van Leeuwen (Linking Roots)	1976	$O(n+m*log(log(n)$))	$O(n)$	Exact	Deterministic	Space
Sleator and Tarjan (Linking)	1983	$O(n+m*log(n)$)	$O(n)$	Exact	Deterministic	Time & Space
Sleator and Tarjan (Linking and Cutting)	1983	$O(n+m*log(n)$)	$O(n)$	Exact	Deterministic	Time & Space
Harel, Tarjan (Linking Roots)	1984	$O(n+ m*alpha(m + n, n)$) where alpha is the inverse Ackermann function	$O(n)$	Exact	Deterministic	Time & Space