DisjointSetUnion#

class DisjointSetUnion(iterable=None)#

Bases: object

Union–Find / Disjoint Set Union (DSU).

Manages a partition of elements into disjoint sets and supports: adding elements, finding a set representative, uniting two sets, iterating over components, and exporting components.

Parameters:: iterable (Iterable[Hashable] | None) – Optional iterable of elements to initialize as singleton sets.

Example

>>> dsu = DisjointSetUnion([1, 2, 3])
>>> dsu.union(1, 2)
>>> dsu.find(1) == dsu.find(2)
True
>>> sorted(sorted(g) for g in dsu)
[[1, 2], [3]]

__init__(iterable=None)#

Parameters:: iterable (Iterable[Hashable] | None)
Return type:: None

Methods

`__init__`([iterable])
`add`(item)	Add a new item as a singleton set (no-op if it already exists).
`classes`()	Return a list of all disjoint sets (components).
`find`(item)	Return the representative (root) of the set containing `item`.
`representatives`()	Yield one representative per component (uses `min` for stability).
`to_dict`()	Return a mapping {rep: others} for each component.
`to_set`(item)	Return the component containing `item`.
`union`(item1, item2)	Merge the sets containing `item1` and `item2` (if both exist).

Attributes

elements

Iterate over all elements ever added.

add(item)#

Add a new item as a singleton set (no-op if it already exists).

Parameters:: item (Hashable) – Element to add.
Return type:: None

find(item)#

Return the representative (root) of the set containing item.

Performs path compression for near-constant amortized time.

Parameters:: item (Hashable) – Element to locate.
Returns:: The set representative, or None if the item is unknown.
Return type:: Hashable | None

Example

>>> dsu = DisjointSetUnion([1, 2])
>>> dsu.find(1) in {1, 2}
True

union(item1, item2)#

Merge the sets containing item1 and item2 (if both exist).

Uses union-by-rank heuristic. If either item is unknown, nothing happens.

Parameters:

item1 (Hashable) – First element.
item2 (Hashable) – Second element.

Return type:

None

Example

>>> dsu = DisjointSetUnion([1, 2, 3])
>>> dsu.union(1, 2)
>>> dsu.find(1) == dsu.find(2)
True

property elements: Iterator[Hashable]#

Iterate over all elements ever added.

Returns:: An iterator over elements.

to_set(item)#

Return the component containing item.

Parameters:: item (Hashable) – An element present in the DSU.
Returns:: The set of items in the same component (empty set if item unknown).
Return type:: set[Hashable]

Example

>>> dsu = DisjointSetUnion([1, 2, 3])
>>> dsu.union(1, 2)
>>> dsu.to_set(1) == {1, 2}
True

representatives()#

Yield one representative per component (uses min for stability).

Warning

Elements in a component must be mutually comparable for min to work.

Yields:: A representative element per component.
Return type:: Iterator[Hashable]

classes()#

Return a list of all disjoint sets (components).

Return type:: list[set[Hashable]]

to_dict()#

Return a mapping {rep: others} for each component.

The representative is chosen as min(component) (see caveat in representatives()).

Returns:: A dictionary mapping each representative to the other members in the set.
Return type:: dict[Hashable, set[Hashable]]