Nothing special here. It’s just a blog post for summarising my algorithm learning course.

- Part 1 - Union Find: This post
- Part 2 - Quick Find
- Part 3 - Quick Union
- Part 4 - Improved Quick Union
- Part 5 - Related Interview Questions

# Dynamic Connectivity

## The problem

Given a data structure organised as a set of N objects

- Union command: connect 2 objects.
- Find/connected command: is there a path connecting 2 objects?

Can only answer the question with `Yes`

or `No`

. The `Dynamic Connectivity`

implementation cannot
answer the exact path between 2 objects. It can only answer whether there are any paths connecting 2
objects.

## IsConnected Relation

`IsConnected`

relation has these properties

- Reflexive: p is connected to p.
- Symmetric: if p is connected to q, then q is connected to p.
- Transitive: if p is connected to q and q is connected to r, then p is connected to r.

## Connected Components

Maximal set of objects that are mutually connected

3 connected components

- { 0 }
- { 1 4 5 }
- { 2 3 6 7 }

# Union Find

The Union Find data type contains these 2 main methods

`UF(int N)` |
initialize union-find data structure with N objects (0 to N – 1) |

`void union(int p, int q)` |
add connection between p and q |

`boolean connected(int p, int q)` |
are p and q in the same component? |