# 1. Union-Find & Applications

**WIP:**I am still migrating the notes to this site

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