Disjoint Sets

Union-Find Data Structure

Two optimization strategies:

1. Path compression

2. Union by rank

   Initially a set has one element and a rank of zero. If two sets are unioned and have the same rank, the resulting set's rank is one larger

Amortized Complexity

Algorithm	Average	Worst case
Space	$O(n)$	$O(n)$
Find	$O(\alpha (n))$	$O(\alpha (n))$
Union	$O(\alpha (n))$	$O(\alpha (n))$

$\alpha (\cdot )$ is inverse Ackermann function, for the generally possible value n, $\alpha (n)$ is less than 5

Tests