Class UnionFind<T>

• Type Parameters:
T - element type

public class UnionFind<T>
extends Object
An implementation of Union Find data structure. Union Find is a disjoint-set data structure. It supports two operations: finding the set a specific element is in, and merging two sets. The implementation uses union by rank and path compression to achieve an amortized cost of $O(\alpha(n))$ per operation where $\alpha$ is the inverse Ackermann function. UnionFind uses the hashCode and equals method of the elements it operates on.
Author:
Tom Conerly
• Constructor Summary

Constructors
Constructor Description
UnionFind​(Set<T> elements)
Creates a UnionFind instance with all the elements in separate sets.
• Method Summary

All Methods
Modifier and Type Method Description
Adds a new element to the data structure in its own set.
T find​(T element)
Returns the representative element of the set that element is in.
protected Map<T,​T> getParentMap()
protected Map<T,​Integer> getRankMap()
boolean inSameSet​(T element1, T element2)
Tests whether two elements are contained in the same set.
int numberOfSets()
Returns the number of sets.
void reset()
Resets the UnionFind data structure: each element is placed in its own singleton set.
int size()
Returns the total number of elements in this data structure.
String toString()
Returns a string representation of this data structure.
void union​(T element1, T element2)
Merges the sets which contain element1 and element2.
• Constructor Detail

• UnionFind

public UnionFind​(Set<T> elements)
Creates a UnionFind instance with all the elements in separate sets.
Parameters:
elements - the initial elements to include (each element in a singleton set).
• Method Detail

Adds a new element to the data structure in its own set.
Parameters:
element - The element to add.
• getParentMap

protected Map<T,​T> getParentMap()
Returns:
map from element to parent element
• getRankMap

protected Map<T,​Integer> getRankMap()
Returns:
map from element to rank
• find

public T find​(T element)
Returns the representative element of the set that element is in.
Parameters:
element - The element to find.
Returns:
The element representing the set the element is in.
• union

public void union​(T element1,
T element2)
Merges the sets which contain element1 and element2. No guarantees are given as to which element becomes the representative of the resulting (merged) set: this can be either find(element1) or find(element2).
Parameters:
element1 - The first element to union.
element2 - The second element to union.
• inSameSet

public boolean inSameSet​(T element1,
T element2)
Tests whether two elements are contained in the same set.
Parameters:
element1 - first element
element2 - second element
Returns:
true if element1 and element2 are contained in the same set, false otherwise.
• numberOfSets

public int numberOfSets()
Returns the number of sets. Initially, all items are in their own set. The smallest number of sets equals one.
Returns:
the number of sets
• size

public int size()
Returns the total number of elements in this data structure.
Returns:
the total number of elements in this data structure.
• reset

public void reset()
Resets the UnionFind data structure: each element is placed in its own singleton set.
• toString

public String toString()
Returns a string representation of this data structure. Each component is represented as $\left{v_i:v_1,v_2,v_3,...v_n\right}$, where $v_i$ is the representative of the set.
Overrides:
toString in class Object
Returns:
string representation of this data structure