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.

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.

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.

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

Make a new subset containing x if any existing subset of s does not contain x.

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.

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.

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.

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

Find the root element of the subset that contains an member x. Path compression happens here.

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.

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.

num_sets(s::DisjointSet)

Get the number of sets.

num_sets(s::IntDisjointSet)

Get a number of sets.

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).

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).

set_size(s::DisjointSet{T}, x::T)

Returns the size of the set that x is in.

set_size(s::IntDisjointSet{T}, x::T)

Returns the size of the set that x is in.