What is Union-Find or Disjoint Set Data Structure
π‘ Concept Name
Union-Find / Disjoint Set β A data structure used to efficiently group elements into disjoint sets and quickly determine whether elements belong to the same set.
π Quick Intro
Union-Find is primarily used in algorithms that deal with dynamic connectivity like Kruskalβs Minimum Spanning Tree or detecting cycles in graphs. It consists of two main operations: find and union.
π§ Analogy / Short Story
Imagine tracking social groups. When two people meet and become part of the same friend group, we merge their groups. Later, we may ask: "Are these two people in the same friend circle?" Thatβs Union-Find!
π§ Technical Explanation
- π Find: Returns the representative (parent) of the set an element belongs to.
- π Union: Merges two sets by linking their representatives.
- πͺ Path Compression: Speeds up future queries by flattening the tree structure during find operations.
- π Union by Rank: Keeps the tree shallow by attaching the smaller tree under the taller one.
- β±οΈ Time Complexity: Near constant O(Ξ±(n)) using both path compression and union by rank.
π― Purpose & Use Case
- β Cycle detection in graphs
- β Kruskalβs algorithm for MST
- β Dynamic connectivity queries
- β Network connectivity checks
π» Real Code Example
class UnionFind
{
private int[] parent;
private int[] rank;
public UnionFind(int size)
{
parent = new int[size];
rank = new int[size];
for (int i = 0; i < size; i++)
parent[i] = i;
}
public int Find(int x)
{
if (parent[x] != x)
parent[x] = Find(parent[x]); // Path Compression
return parent[x];
}
public void Union(int x, int y)
{
int xRoot = Find(x);
int yRoot = Find(y);
if (xRoot == yRoot) return;
if (rank[xRoot] < rank[yRoot])
parent[xRoot] = yRoot;
else if (rank[xRoot] > rank[yRoot])
parent[yRoot] = xRoot;
else
{
parent[yRoot] = xRoot;
rank[xRoot]++;
}
}
}
β Interview Q&A
Q1: What is the Union-Find or Disjoint Set Union (DSU) data structure?
A: A data structure that keeps track of elements partitioned into disjoint sets and supports union and find operations efficiently.
Q2: What are the two main operations in DSU?
A: Find (to identify which set an element belongs to) and Union (to merge two sets).
Q3: How does the Find operation work?
A: It returns the representative or parent of the set containing the element.
Q4: What is path compression in DSU?
A: An optimization technique that flattens the structure of the tree during Find operations to speed up future queries.
Q5: What is union by rank or size?
A: An optimization that always attaches the smaller tree under the root of the larger tree during union.
Q6: What is the time complexity of DSU operations with optimizations?
A: Nearly O(1) amortized, often described as inverse Ackermann function, practically constant.
Q7: What are common use cases of DSU?
A: Cycle detection in graphs, Kruskalβs MST algorithm, network connectivity.
Q8: How is DSU represented internally?
A: Usually by an array where each element points to its parent.
Q9: Can DSU handle dynamic insertion of new elements?
A: Typically no; DSU is static but can be adapted with dynamic techniques.
Q10: Why is DSU preferred over other methods for connectivity problems?
A: Because it provides efficient union and find operations with near constant time.
π MCQs
Q1. What does DSU stand for?
- Disjoint Set Union
- Direct Set Union
- Disjoint Sorted Union
- Dynamic Set Union
Q2. What are the main operations in DSU?
- Insert and Delete
- Find and Union
- Search and Sort
- Add and Remove
Q3. What does Find operation return?
- Element value
- Set representative
- Set size
- Root node data
Q4. What is path compression?
- Sorting technique
- Optimization to flatten trees
- Union technique
- Search method
Q5. What is union by rank?
- Attach larger tree to smaller
- Attach smaller tree to larger
- Merge randomly
- No merging
Q6. What is the amortized time complexity of DSU operations?
- O(n)
- O(log n)
- Nearly O(1)
- O(n log n)
Q7. Which algorithm commonly uses DSU?
- Dijkstra's
- Kruskal's MST
- Prim's MST
- Bellman-Ford
Q8. How is DSU internally represented?
- Linked list
- Parent array
- Stack
- Queue
Q9. Can DSU handle dynamic insertion?
- Yes
- Generally no
- Only in trees
- Only in graphs
Q10. Why is DSU efficient for connectivity problems?
- Slow union and find
- Fast union and find
- Uses hashing
- Uses sorting
π‘ Bonus Insight
Union-Find is not just useful in graphs. It is also used in image processing (for connected components), clustering algorithms, and even in puzzles like Sudoku to ensure group constraints.
π PDF Download
Need a handy summary for your notes? Download this topic as a PDF!