# Disjoint Set Union

Works in $O(gn)$ time.

- Always connect the representative of the smaller set to the representative of the larger set (or if the sets are of equal size, we can make an arbitrary choice).

### Implementation

`link`

contains for each element the next element in the chain or the element itself if it is a representative`size`

indicates for each representative the size of the corresponding set

### Optimizations

**Path Compression Optimization**
The `find`

function is naive and can take $O(n)$. We can optimize it so every time you call find, you update the parent directly to the root.

This allows us to achieve $O(gn)$ on average.

**2. Union by size (already implemented)** in the logic above

### Applications

- Kruskalâ€™s Algorithm for finding the Minimum Spanning Tree