E - the type of the elementspublic class DisjointSets<E> extends Object
This data structure is used to maintain disjoint sets. It supports limited number of operations, but they are all executed in constant amortized time. The supported operations are:
The space taken by this structure is O(n), where n is the number of elements.
| Constructor and Description |
|---|
DisjointSets()
Creates a new instance containing no sets and no elements
|
DisjointSets(int initialCapacity)
Creates a new instance containing no sets and no elements.
|
| Modifier and Type | Method and Description |
|---|---|
boolean |
add(E e)
Adds a new set containing only
e to the structure. |
void |
clear()
Reinitializes the structure.
|
boolean |
contains(Object e)
Checks if an element belongs to some of the disjoint sets.
|
boolean |
inSameSet(Object e1,
Object e2)
Checks if two elements belong to the same set.
|
boolean |
union(Object e1,
Object e2)
Union of the set containing
e1 and the set containing e2. |
public DisjointSets()
public DisjointSets(int initialCapacity)
initialCapacity - Initial capacity (in number of elements) of the structure. The
structure grows dynamically and new elements can be added even
if this capacity is exceeded.public boolean add(E e)
e to the structure. If e
already belongs to some of the disjoint sets, nothing happens.e - The element to add as a singletone already
belongs to some set.public boolean inSameSet(Object e1, Object e2)
e1 - An elemente2 - An elemente1 or e2 do not belong to any set, false is
returned.public boolean union(Object e1, Object e2)
e1 and the set containing e2.
After this operation inSameSet(e1, e2) will return true. If
e1 or e2 do not belong to any set or if they already
belong to the same set, nothing happens.e1 - An elemente2 - An elementtrue if and only if e1 and e2 belong to different sets at the beginningpublic boolean contains(Object e)
e - An elemente belongs to some set.public void clear()
Copyright © 2015. All rights reserved.