Disjoint Set

class pydatastructs.DisjointSetForest

Represents a forest of disjoint set trees.

Examples

>>> from pydatastructs import DisjointSetForest
>>> dst = DisjointSetForest()
>>> dst.make_set(1)
>>> dst.make_set(2)
>>> dst.union(1, 2)
>>> dst.find_root(2).key
1
>>> dst.make_root(2)
>>> dst.find_root(2).key
2

References

1

https://en.wikipedia.org/wiki/Disjoint-set_data_structure

make_set(key, data=None)

Adds a singleton set to the tree of disjoint sets with given key and optionally data.

find_root(key)

Finds the root of the set with the given key by path splitting algorithm.

union(key1, key2)

Takes the union of the two disjoint set trees with given keys. The union is done by size.

make_root(key)

Finds the set to which the key belongs and makes it as the root of the set.

tree

__module__ = 'pydatastructs.miscellaneous_data_structures.disjoint_set'