# union-find

These are notes from a great course on algorithms.

# Slides

# Use Case

Give a set of objects, determine if they are connected

# Interface

`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?`int find(int p)`

: component identifier for p (0 to N – 1)`int count()`

: number of components

# Quick find implementation

Use integer array id[] of length N p and q are connected if they have same id id[p]==id[q]

`UF(int N)`

:`id[i]=i`

`boolean connected(int p, int q)`

:`id[p]==id[q]`

`void union(int p, int q)`

: change all id[p] to id[q]

# Quick union (lazy)

Use integer array id[] of length N id[i] is the parent of i Root of i id id[id[id[…id[i]…]]]

`UF(int N)`

:`id[i]=i`

`boolean connected(int p, int q)`

: Check if p and q have the same root.`root(p) == root(q)`

`void union(int p, int q)`

: To merge components containing p and q, set the id of p’s root to the id of q’s root.`id[root(p)]=root(q)`

- private
`int root(int i)`

: iterate i=id[i] until i==id[i]

Issue: trees can become too deep

# Quick union (weighted)

Add an array to track size of item at i

`UF(int N)`

:`id[i]=i`

`boolean connected(int p, int q)`

: Check if p and q have the same root.`root(p) == root(q)`

`void union(int p, int q)`

: Link root of smaller tree to root of larger tree`int i = root(p); int j = root(q); if (i == j) return; if (sz[i] < sz[j]) { id[i] = j; sz[j] += sz[i]; } else { id[j] = i; sz[i] += sz[j]; }`

- private
`int root(int i)`

: iterate i=id[i] until i==id[i]

Analysis: Running time.

- Find: takes time proportional to depth of p and q.
- Union: takes constant time, given roots. Proposition. Depth of any node x is at most lg N.

# Quick union (path compression)

*Quick union with path compression*: Just after computing the root of p,
set the id of each examined node to point to that root.

*Two-pass implementation*: add second loop to root() to set the id[]
of each examined node to the root.

*Simpler one-pass variant*: Make every other node in path point to its
grandparent (thereby halving path length)

`UF(int N)`

:`id[i]=i`

`boolean connected(int p, int q)`

: Check if p and q have the same root.`root(p) == root(q)`

`void union(int p, int q)`

: Link root of smaller tree to root of larger tree`int i = root(p); int j = root(q); if (i == j) return; if (sz[i] < sz[j]) { id[i] = j; sz[j] += sz[i]; } else { id[j] = i; sz[i] += sz[j]; }`

- private
`int root(int i)`

: iterate i=id[i] until i==id[i]

Analysis: Running time.

- Find: takes time proportional to depth of p and q.
- Union: takes constant time, given roots. Proposition. Depth of any node x is at most lg N.

# Analysis

algorithm | initialize | union | find |

quick-find | N | N | 1 |

quick-union | N | N | N |

quick-union (weighted) | N | lg N | lg N |