A disjoint-set data structure, also called a union–find data structure or merge–find set.

A disjoint-set data structure that keeps track of a set of elements partitioned into a number of disjoint or non-overlapping subsets.

It provides near-constant-time operations to add new sets, to merge existing sets, and to determine whether elements are in the same set.

Plays a key role in Kruskal’s algorithm for finding the minimum spanning tree of a graph.

This can also be used to detect cycle in the graph.

How Disjoint Set is constructed:

A disjoint-set forest consists of a number of elements each of which stores an id, a parent pointer

The parent pointers of elements are arranged to form one or more trees, each representing a set.

If an element’s parent pointer points to no other element, then the element is the root of a treeand is the representative member of its set.

A set may consist of only a single element. However, if the element has a parent, the element is part of whatever set is identified by following the chain of parents upwards until a representative element (one without a parent) is reached at the root of the tree.

Disjoint Set Operations:

MakeSet(X): This operation makes a new set by creating a new element with a parent pointer to itself. The parent pointer to itself indicates that the element is the representative member of its own set. The MakeSet operation has O(1) time complexity.

Find(X): follows the chain of parent pointers from x upwards through the tree until an element is reached whose parent is itself. This element is the root of the tree and is the representative member of the set to which x belongs, and may be x itself.

Union(x,y): Uses Find to determine the roots of the trees x and y belong to. If the roots are distinct, the trees are combined by attaching the root of one to the root of the other. If this is done naively, such as by always making x a child of y, the height of the trees can grow as O(n).

If you find anything incorrect or you feel that there is any better approach to solve the above problem, please write comment.
__________________________________________________

Try in incognito, if it works in incognito then try clearing ur cache and reload the page. let us know if it is still not working

lipsa patel

Was this question asked in any company interview?

tutorialhorizon

Union – Find is a concept which us widely used in many problem solving like detect cycle in graph, krushkal algorithm etc. I will be posting articles (in next few days )which uses this concept. Thanks for following

lipsa patel

“always making x a child of y” in Union operation should be
“always making y a child of x”. This what is done in code.