Package Struct
Class DSU
java.lang.Object
Struct.DSU
Represents a Disjoint Set Union (DSU) also known as Union-Find data structure.
It supports union and find operations, to determine which set a particular element
is in, and to unite two sets if they are disjoint.
- Since:
- 1.0
- Version:
- 1.0
- Author:
- Sahasrad Chippa
-
Constructor Summary
ConstructorsConstructorDescriptionDSU
(int n) Initializes the DSU with n elements, each element is its own set initially. -
Method Summary
Modifier and TypeMethodDescriptionboolean
connected
(int x, int y) Checks if the elements 'x' and 'y' are in the same set.int
find
(int x) Finds the representative of the set that x is a part of.boolean
Checks if all elements are part of a single set.boolean
union
(int x, int y) Unites the set that includes 'x' with the set that includes 'y'.
-
Constructor Details
-
DSU
public DSU(int n) Initializes the DSU with n elements, each element is its own set initially. Runs inO(n)
.- Parameters:
n
- The total number of elements.
-
-
Method Details
-
find
public int find(int x) Finds the representative of the set that x is a part of. Uses path compression to flatten the structure of the tree whenever it is used, leading to very efficient queries. Runs inO(α(n))
, where α is the inverse Ackermann function.- Parameters:
x
- The element to find.- Returns:
- The representative item of the set containing 'x'.
-
union
public boolean union(int x, int y) Unites the set that includes 'x' with the set that includes 'y'. Uses union by size, ensuring the smaller set points to the representative of the larger set. Runs inO(α(n))
, where α is the inverse Ackermann function.- Parameters:
x
- First element.y
- Second element.- Returns:
- true if the union was successful and the elements were previously in different sets, false otherwise.
-
connected
public boolean connected(int x, int y) Checks if the elements 'x' and 'y' are in the same set. Runs inO(α(n))
, where α is the inverse Ackermann function.- Parameters:
x
- First element.y
- Second element.- Returns:
- true if 'x' and 'y' are in the same set, false otherwise.
-
fullyConnected
public boolean fullyConnected()Checks if all elements are part of a single set. Runs inO(1)
.- Returns:
- true if all elements are in one set, false otherwise.
-