`DisjointSets.DisjointSet`

— Type`DisjointSet{T}(xs)`

A forest of disjoint sets of arbitrary value type `T`

. It is a wrapper of `IntDisjointSet{Int}`

, which uses a dictionary to map the input value to an internal index.

`DisjointSets.IntDisjointSet`

— Type`IntDisjointSet{T<:Integer}(n::Integer)`

A forest of disjoint sets of integers, which is a data structure (also called a union–find data structure or merge–find set) that tracks a set of elements partitioned into a number of disjoint (non-overlapping) subsets.

`Base.push!`

— Method`push!(s::IntDisjointSet{T})`

Make a new subset with an automatically chosen new element `x`

. Returns the new element. Throw an `ArgumentError`

if the capacity of the set would be exceeded.

`Base.push!`

— Method`push!(s::DisjointSet{T}, x::T)`

Make a new subset containing `x`

if any existing subset of `s`

does not contain `x`

.

`Base.union!`

— Method`union!(s::DisjointSet{T}, x::T, y::T)`

Merge the subset containing `x`

and that containing `y`

into one and return the root of the new set.

`Base.union!`

— Method`union!(s::IntDisjointSet{T}, x::T, y::T)`

Merge the subset containing `x`

and that containing `y`

into one and return the root of the new set.

`DisjointSets.find_root!`

— Method`find_root!{T}(s::DisjointSet{T}, x::T)`

Find the root element of the subset in `s`

which has the element `x`

as a member.

`DisjointSets.find_root!`

— Method`find_root!(s::IntDisjointSet{T}, x::T)`

Find the root element of the subset that contains an member `x`

. Path compression happens here.

`DisjointSets.in_same_set`

— Method`in_same_set(s::DisjointSet{T}, x::T, y::T)`

Return `true`

if `x`

and `y`

belong to the same subset in `s`

, and `false`

otherwise.

`DisjointSets.in_same_set`

— Method`in_same_set(s::IntDisjointSet{T}, x::T, y::T)`

Returns `true`

if `x`

and `y`

belong to the same subset in `s`

, and `false`

otherwise.

`DisjointSets.num_sets`

— Method`num_sets(s::DisjointSet)`

Get the number of sets.

`DisjointSets.num_sets`

— Method`num_sets(s::IntDisjointSet)`

Get a number of sets.

`DisjointSets.root_union!`

— Method`root_union!(s::DisjointSet{T}, x::T, y::T)`

Form a new set that is the union of the two sets whose root elements are `x`

and `y`

and return the root of the new set. Assume `x ≠ y`

(unsafe).

`DisjointSets.root_union!`

— Method`root_union!(s::IntDisjointSet{T}, x::T, y::T)`

Form a new set that is the union of the two sets whose root elements are `x`

and `y`

and return the root of the new set. Assume `x ≠ y`

(unsafe).

`DisjointSets.set_size`

— Method`set_size(s::DisjointSet{T}, x::T)`

Returns the size of the set that `x`

is in.

`DisjointSets.set_size`

— Method`set_size(s::IntDisjointSet{T}, x::T)`

Returns the size of the set that `x`

is in.