Disjoint-set data structure

[czgdp1807]

Description of the problem

Disjoint set data structure can have the following APIs,

Set
The class Set will represent the notion of disjoint sets with respect to the above data structure.
Attributes

1. key - Any valid key which can be used to uniquely identify this set.
2. data - Any valid data or pointers to data can be stored through this.
3. parent - The parent of this set.
4. size - The size of the set.
5. rank - The rank of the set.

We cannot use static data classes as the data attribute will be dynamic.

DisjointSetTree
This will represent the notion of disjoint set tree of DisjointSet.
Attribute
tree - A python dict for key to DisjointSet mapping. Hashing here will help us quickly figure out whether a DisjointSet is there inside the tree.

Methods

1. make_set(key, data) - It will make a new set as described in the references.
2. find(key) - Finding the root of a particular disjoint set sub tree using path-splitting logic.
3. union(key1, key2) - Taking union of sets with given keys by size.

Example of the problem

References/Other comments

.. [1] https://en.wikipedia.org/wiki/Disjoint-set_data_structure

This is not open for contributions.

[abhishekgupta368]

I can do it efficiently, Can you please assign me?

[robotjellyzone]

Hi @abhishekgupta368 , are you a participant of GSSOC'20 ?

[czgdp1807]

This issue is not open for contributors as written in the description.

[abhishekgupta368]

yes, I am participant of GSSOC'20