DisjointSetUnion#

class DisjointSetUnion(iterable=None)#

Bases: object

A Disjoint Set Union (DSU), also known as a Union-Find data structure, manages a partition of a set into disjoint (non-overlapping) subsets. It supports finding the set representative, and union operation to merge sets.

Parameters:: iterable (Iterable) – An optional iterable of hashable elements to initialize the DSU.

__init__(iterable=None)#

Initializes the DSU. If elements are provided, each element is initialized in its own set.

Parameters:: iterable (Iterable) – An optional iterable of hashable elements to initialize the DSU.

Methods

`__init__`([iterable])	Initializes the DSU.
`add`(item)	Add an item to the DSU if not already present, initializing its set.
`classes`()
`find`(item)	Finds the representative of the set containing 'item'.
`representatives`()	Iterate over the representatives of each set.
`set`(item)	Returns the set of items connected to 'item'.
`to_dict`()	Convert the DSU to a dictionary mapping each representative to its elements (that are not the representative).
`union`(item1, item2)	Performs the union of the sets that contain set1 and set2.

Attributes

elements

add(item)#: Add an item to the DSU if not already present, initializing its set.

find(item)#

Finds the representative of the set containing ‘item’.

Parameters:: item (Hashable) – The item to find.
Returns:: The representative of the set containing ‘item’.
Return type:: Hashable

representatives()#: Iterate over the representatives of each set.

set(item)#

Returns the set of items connected to ‘item’.

Parameters:: item (Hashable) – Any member of the set.
Returns:: A set containing all items in the connected component of ‘item’.
Return type:: set

to_dict()#: Convert the DSU to a dictionary mapping each representative to its elements (that are not the representative).

union(item1, item2)#

Performs the union of the sets that contain set1 and set2.

Parameters:

item1 (Hashable) – An element of the first set.
item2 (Hashable) – An element of the second set.