Union Find Algorithm

Imagine:

- you have a set of n objects
- where objects can have some sort of connection between them
- and you want to determine if there is a path between two objects.

We assume that the connection between two of these objects is reflexive, symmetric and transitive.

How could this be implemented?

Basically, you can maintain disjointed subsets of components illustrating which are transitively connected.

Eg:

In this example the division of nodes would be: {0, 3, 4, 8} {1} {2, 5} {6, 7}

Implementation 1: Bias towards find

You could store it in an array showing the relationships:

[0, 1, 2, 0, 0, 2, 3, 3, 0]

 (eg elements at index 2 and index 5 are both two meaning they are in the same subset)

With this algorithm find is O(1) but union is O(n) which is still a bit slow.

Implementation 2: Maintain little trees

Again maintain an array but this time it is an array of little trees. 

Start with [0, 1, 2, 3, 4, 5, 6, 7, 8]

union(2,3) => Update 2 to have root 3: [0, 1, 3, 3, 4, 5, 6, 7, 8]

union(3, 8) => Update 3 to have root 8:  [0, 1, 3, 8, 4, 5, 6, 7, 8]

union(1, 6) => Update 1 to have root 6:  [0, 6, 3, 8, 4, 5, 6, 7, 8]

union(7, 3) => Update 7 to have root 8 (3's root):  [0, 6, 3, 8, 4, 5, 6, 7, 8]

With this implementation both find and union are worst case O(n) 

Improvements

The problem with implementation 2 is that your little trees can end up not so little and can get very tall. There are some optimisations you can do to improve performance to minimise tree depth.