# MutDisjointSets

`enum MutDisjointSets[t: Type, r: Eff]`

Source`case MutDisjointSets({ forest = MutMap[t, Node[t, r], r], rc = Region[r] })`

Represents a mutable disjoint set data structure using union-by-rank and path compression.

## Definitions

Returns true if `x`

and `y`

are in the same disjoint set.
This is equivalent to having the same representative / root.
Returns false if either `x`

or `y`

is not in `s`

.

Returns the representative / root of the set that contains `x`

.

Updates `s`

with a new disjoint set containing `x`

if `x`

is not already in `s`

.

Updates `s`

with the elements of the iterable `m`

.

Returns `true`

iff `x`

is a member of `s`

.

`def new(rc: Region[r]): MutDisjointSets[t, r] \ r`

SourceReturns the number of elements in `s`

.

Merges the sets that contain `x`

and `y`

if both `x`

and `y`

are in `s`

.
If `x`

and `y`

have the same rank, then `y`

becomes the new parent of `x`

.
Otherwise, the element with the highest rank becomes the new representative.

The rank of an element is determined by how many times it is made the new representative after a union with another element of the same rank.

Further reading:
https://en.wikipedia.org/wiki/Disjoint-set*data*structure