• Algorithm: method for solving a problem
• Data structure: method to store information

Union Find

• model the problem
• find an algorithm to solve it
• fast enough? fits in memory
• if not figure out why
• find a way to address the problem
• iterate until satisfied

Dynamic Connectivity

modeling the objects
When programming, convenient to name objects 0 to N-1

• use integers as array index
• suppress details not relevant to union-find.

modeling the connections
We assume “is connected to” is an equivalence relation:

• 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

Implementing the operations
Find query

• check if two objects are in the same component
  Union command
• Replace components containing two objects with their union