## Disjoint Sets¶

Signature | Description |
---|---|

`void makeSet(T item)` | Creates a new set containing just the given item and with a new integer id. |

`int findSet(T item)` | Returns the integer id of the set containing the given item. |

`boolean union(T item1, T item2)` | If the given items are in different sets, merges those sets and returns `true` . Otherwise does nothing and returns `false` . |

The `disjointsets`

package contains the disjoint sets data structures required by Kruskalâ€™s algorithm. We include a default, inefficient implementation in the skeleton.

The inefficient implementation will be replaced by the optimized `UnionBySizeCompressingDisjointSets`

implementation to generate mazes.

## An Optimized Implementation¶

Task

Implement `UnionBySizeCompressingDisjointSets`

using union-by-size, path compression, and array representation optimizations.

Implementation notes:

- We recommend reviewing the lecture slides and section materials before implementing your disjoint sets.
- The Gradescope tests will directly inspect the
`pointers`

field so be sure to store the array representation of your disjoint sets there.

In the next section, you will use your optimized disjoint sets implementation to speed up `KruskalMinimumSpanningTreeFinder`

.