1. Union-Find & Applications
Table of Contents
1. Dynamic Connectivity
1.1 Problem statement
Given a set of objects and connections, find whether two objects are connected.
A connection between objects can be transitive, i.e object $p$ can be connected $s$ if $p$ is connected to $q$ and $q$ is connected to $s$.
Operations:
The following are the expected basic operators required for the desired data structure:
connected() -> bool: Check if two objects are in the same component.union() -> None: adds a connection between two objects.
Therefore the goal can be summarized as following:
Goal: Design efficient data structure for to check the connectivity between two objects (union-find).
Constraints:
- Number of objects N can be huge
- Number of operations M can be huge
- Find queries and union commands may be intermixed
1.2 Modeling the objects
The fundamental aspect of designing the data structure is to suppress details that are not relevant to union-find.
There are several way to achieve this goal, however the simplest method is to model Objects as integers. These integers are used as an array index. Another method is to use a symbol table to translate from objects to integers.
1.3 Modeling the connections
A connection is assumed to be 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: Set of objects that are mutually connected.