Introduction

Disjoint Set, also known as Union-Find, is an important data structure in Data Structures and Algorithms (DSA) used to manage connected components efficiently. If you are enrolled in a DSA course in Jaipur, mastering Union-Find will help you solve graph problems like cycle detection and connectivity.

It is widely used in graph algorithms and competitive programming.

What is Disjoint Set (Union-Find)?

Disjoint Set is a data structure that keeps track of elements divided into separate sets.

It supports two main operations:

• Find → Determine which set an element belongs to
• Union → Merge two sets

Example

Elements: {1, 2, 3, 4, 5}

Initially:

• Each element is in its own set

After unions:

• Union(1,2) → {1,2}
• Union(3,4) → {3,4}
• Union(2,3) → {1,2,3,4}

Core Operations

1. Find Operation

• Returns representative (parent) of a set

2. Union Operation

• Combines two sets

Path Compression

parent[x]=find(parent[x])

• Flattens tree structure
• Speeds up future operations

Union by Rank

• Attach smaller tree under larger tree
• Reduces height

Time Complexity

$O(\alpha (n))$

• Nearly constant time
• α(n) is inverse Ackermann function

Advantages

• Very fast operations
• Efficient for connectivity problems
• Easy to implement
• Optimized with path compression

Disadvantages

• Limited use cases
• Requires understanding of trees

Real-World Applications

• Network connectivity
• Cycle detection in graphs
• Kruskal’s algorithm
• Social network grouping

Common Interview Questions

• Implement Union-Find
• Detect cycle in graph
• Number of connected components
• Kruskal’s MST

Best Practices

• Always use path compression
• Use union by rank
• Practice graph problems
• Optimize operations

Summary

• Disjoint set manages multiple sets
• Uses union and find operations
• Optimized using path compression
• Time complexity is nearly O(1)
• Important for graph problems

FAQs

Q1. What is Union-Find?
It is a data structure to manage disjoint sets.

Q2. What is path compression?
It flattens the tree for faster operations.

Q3. What is union by rank?
It attaches smaller tree to larger one.

Q4. What is time complexity?
Nearly O(1).

Q5. Is it important for interviews?
Yes, especially for graph problems.

Internal Link

To explore more programming and development courses, click here for more free courses.