# Union-Find

## Quick-find [Eager approach]

### Data Structure

- Integer array
**id[]**of size N. - Interpretation: p and q are connected
**iff**they have the same id

### Find

Check if p and q have the same id.

1 | ie. |

### Union

To merge components containing p and q, change all entries whose id equals id[p] to id[q]

### Implementation

1 | public class QuickFindUF { |

### Efficiency

Cost model: Number of array accesses (for read or write)

Algogrthim | Initialize | Union | Find |
---|---|---|---|

Quick-find | N | N | 1 |

**Quick-find defect**:

Union too expensive.

Trees are flat, but too expensive to keep them flat

**Takes $N^2$ array accesses to process sequence of $N$ union commands on $N$ objects**

## Quick Union [Lazy Approach]

### Data Structure

- Integer array
**id[]**of size**N**. - Interpretation:
**id[]**is parent of**i**. **Root**of**i**is**id[id[id[…id[i]…]]]**<- (keep going until it doesn’t change (Algorithm ensures no cycles))

### Find

Check if p and q have the same root

### Union

To merge components containing p and q, set the id of p’s root to the id of q’s root.

### Implementation

1 | public class QuickUnionUF { |

### Efficiency

Cost model: Number of array accesses (for read or write)

Algogrthim | Initialize | Union | Find |
---|---|---|---|

Quick-union | N | N* | N <- worst case |

ps: * includes cost of finding roots

**Quick-union defect**:

- Trees can get tall
- Find too expensive (could be
**N**array access)

## Improvement 1 - Weighting

### Weighted quick-union

- Modify quick-union to avoid tall trees.
- Keep track of size of each tree (
**Number of objects**) - Balance by linking root of smaller tree to root of larger tree.

### Data Structure

- Same as quick-union, but maintain extra array
**sz[i]**to count number of objects in the tree rooted at i.

### Find

Identical to quick-union

### Union

Modify quick-union to:

- Link root of smaller tree to root of larger tree
- Update the sz[] array.

### Implementation

1 | public class WeightedQuickUnionUF { |

### Efficiency

Running Time:

- Find: takes time proportional to depth of p and q
- Union: takes constant time, given roots.

Algogrthim | Initialize | Union | Find |
---|---|---|---|

Weighted QU | N | lgN * | lgN |

ps: * includes cost of finding roots

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

### Implementation

1 | // Two pass: add second loop to root() to set the id[] |

#### Note:

Linear-time algorithm for M union-find ops on N objects?

- Cost within constant factor of reading in the data.
- In theory, WQUPC is not quite linear.
- In practice, WQUPC is linear.

## Summary

Legend: M union-find operations on a set of N objects

Algogrthim | worst-case-time |
---|---|

quick-find | M N |

quick-union | M N |

Weighted QU | N + MlogN |

QU + Path Compression | N + MlogN |

Weighted QU + Path Compression | N + Mlg*N |

- note: lg*N means the number makes lgN to 1. (inverse Ackerman function)