Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

disjoint
sets
disjoint set
data structure

What is the disjoint-set data structure?

Educative Answers Team

Grokking Modern System Design Interview for Engineers & Managers

Ace your System Design Interview and take your career to the next level. Learn to handle the design of applications like Netflix, Quora, Facebook, Uber, and many more in a 45-min interview. Learn the RESHADED framework for architecting web-scale applications by determining requirements, constraints, and assumptions before diving into a step-by-step design process.

The disjoint-set data structure (union-find structure) keeps track of sets that are partitioned into non-overlapping subsets. This disjoint-set structure can be implemented using:

  • Arrays
  • Trees

Methods

  1. Union(a,b): This function takes two indexes and merges their root nodes if they have not been previously merged.
  2. Find(a,b): This function checks if​ two indexes lie in the same set or in two different sets.
  3. makeSet(a): This function makes a new set with the specified element.

Illustration

1 of 5

Since we are left with the two disjoint sets given below, we can use the array to find out if the two indexes lie in the same set or in ​two different sets. If the two indexes have the same parent, then they lie in the same set; otherwise, they are in disjoint sets.

svg viewer

RELATED TAGS

disjoint
sets
disjoint set
data structure
Copyright ©2022 Educative, Inc. All rights reserved

Grokking Modern System Design Interview for Engineers & Managers

Ace your System Design Interview and take your career to the next level. Learn to handle the design of applications like Netflix, Quora, Facebook, Uber, and many more in a 45-min interview. Learn the RESHADED framework for architecting web-scale applications by determining requirements, constraints, and assumptions before diving into a step-by-step design process.

Keep Exploring