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

# 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?