3 stages of union find

Investigated this when doing query optimization.

Naive approach O(N^2)

When doing union and merging new sub-trees, set all sub-tree roots to base root.

For example:

root(1) = 1-2-3
root(3) = 3-4
union(1,3) -- 3 is the new parent

We have to set all of 1’s children to have 3 as their root.

This takes N time since we union N nodes. N time for each union, since we need to iterate over all nodes, and update their root if they have 1 as root (are 1‘s children’).

Better approach O(N)

Use indirect union instead.

Rather than linking all of root(1) children to 3, just link the root 1->3.

This takes O(1) time / union.

Betterer approach O(log2N)

Source: https://www.hackerearth.com/practice/notes/disjoint-set-union-union-find/