Disjoint set (Union-Find) in Data Structures Theory - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is a Disjoint Set (Union-Find) data structure?

A Disjoint Set, also called Union-Find, is a data structure that keeps track of a group of elements split into separate, non-overlapping sets. It helps quickly find which set an element belongs to and merge two sets together.

beginner

What are the two main operations of a Disjoint Set?

The two main operations are: 1) Find - to identify which set an element belongs to, and 2) Union - to merge two sets into one.

intermediate

Why is path compression important in Union-Find?

Path compression speeds up the Find operation by making elements point directly to the root of their set. This reduces the time needed for future Find operations.

intermediate

What does 'union by rank' mean in the context of Disjoint Sets?

Union by rank means always attaching the smaller tree under the root of the larger tree during a Union operation. This keeps the tree shallow and operations fast.

beginner

Give a real-life example where Disjoint Set (Union-Find) can be applied.

Disjoint Set can be used to manage social network friend groups, where each group is a set. When two people become friends, their groups merge. It helps quickly check if two people are in the same friend group.

What does the Find operation in a Disjoint Set do?

A Merges two sets into one

B Deletes an element from a set

C Identifies which set an element belongs to

D Creates a new set with one element

The Find operation tells us which set a particular element belongs to.

What is the main goal of path compression in Union-Find?

A To speed up future Find operations

B To create new sets

C To delete sets quickly

D To make trees taller

Path compression flattens the structure to make Find operations faster.

Union by rank helps to:

A Find elements in constant time

B Delete sets faster

C Create more sets

D Keep trees balanced and shallow

Union by rank attaches smaller trees under larger ones to keep the structure balanced.

Which of these is NOT a typical use of Disjoint Set?

A Tracking connected components in a network

B Sorting a list of numbers

C Managing friend groups in social networks

D Detecting cycles in graphs

Sorting is not related to Disjoint Set operations.

What happens during a Union operation?

A Two sets are merged into one

B An element is removed from a set

C A new set is created

D The Find operation is performed

Union merges two separate sets into a single set.

Explain how the Disjoint Set data structure works and why it is useful.

Think about how groups of friends merge or how network connections are tracked.

Describe the optimizations 'path compression' and 'union by rank' and their benefits.

These techniques keep the structure efficient and fast.

Practice

1. What is the main purpose of a Disjoint Set (Union-Find) data structure?

easy

A. To sort elements in ascending order

B. To store key-value pairs for fast lookup

C. To efficiently keep track of which elements belong to which groups

D. To perform arithmetic calculations on sets

Solution

1. Step 1: Understand the role of Disjoint Set

   Disjoint Set is designed to manage groups of elements and quickly find which group an element belongs to.

2. Step 2: Compare with other options

   Sorting, key-value storage, and arithmetic are unrelated to Disjoint Set's main function.

3. Final Answer:

   To efficiently keep track of which elements belong to which groups -> Option C

4. Quick Check:

   Disjoint Set = group tracking [OK]

Hint: Disjoint Set = fast group membership check [OK]

Common Mistakes:

• Confusing Disjoint Set with sorting algorithms
• Thinking it stores key-value pairs like a dictionary
• Assuming it performs arithmetic on sets

2. Which of the following is the correct way to perform a union operation between two sets containing elements a and b in a Disjoint Set?

easy

A. merge(a, b)

B. union(a, b)

C. unionSet(a, b)

D. combine(a, b)

Solution

1. Step 1: Identify standard Disjoint Set operation names

   The common and standard name for merging two sets is union.

2. Step 2: Check other options

   Other names like unionSet, merge, or combine are not standard and may cause confusion.

3. Final Answer:

   union(a, b) -> Option B

4. Quick Check:

   Union operation = union(a, b) [OK]

Hint: Union operation is always called 'union' [OK]

Common Mistakes:

• Using non-standard method names
• Confusing union with find
• Assuming merge or combine are standard

3. Consider the following sequence of operations on a Disjoint Set with elements {1, 2, 3, 4}:

union(1, 2)
union(3, 4)
union(2, 3)
find(4)

What is the result of find(4)?

medium

A. 4

B. 2

C. 3

D. 1

Solution

1. Step 1: Perform unions step-by-step

   union(1, 2) merges sets {1} and {2} -> {1, 2}. union(3, 4) merges {3} and {4} -> {3, 4}. union(2, 3) merges sets containing 2 and 3 -> {1, 2, 3, 4}.

2. Step 2: Find the representative of element 4

   After unions, all elements are in one set. The representative is usually the root of the first union, which is 1.

3. Final Answer:

   1 -> Option D

4. Quick Check:

   find(4) = 1 after unions [OK]

Hint: After unions, find returns the root representative [OK]

Common Mistakes:

• Assuming find(4) returns 4 itself
• Not merging sets correctly in union(2, 3)
• Confusing element with its set representative

4. Given the following incorrect Disjoint Set code snippet, what is the main error?

def union(a, b):
    rootA = find(a)
    rootB = find(b)
    if rootA != rootB:
        rootA = rootB  # Incorrect assignment

medium

A. The assignment does not update the parent of rootA

B. The find function is called incorrectly

C. The union function should return a value

D. The if condition should check rootA == rootB

Solution

1. Step 1: Analyze the union operation

   The union operation should update the parent of one root to the other to merge sets.

2. Step 2: Identify the error in assignment

   Assigning rootA = rootB only changes the local variable, not the parent array that tracks sets.

3. Final Answer:

   The assignment does not update the parent of rootA -> Option A

4. Quick Check:

   Union must update parent array, not local variables [OK]

Hint: Update parent array, not local variables [OK]

Common Mistakes:

• Assigning roots instead of updating parent array
• Confusing equality check in if condition
• Expecting union to return a value

5. You have 5 elements {1, 2, 3, 4, 5} initially in separate sets. After performing union(1, 2), union(3, 4), and union(2, 3), which of the following statements is true?

hard

A. Elements 1 and 4 belong to the same set

B. Element 5 belongs to the same set as element 1

C. Elements 2 and 5 belong to the same set

D. All elements belong to the same set

Solution

1. Step 1: Track unions step-by-step

   union(1, 2) merges {1, 2}. union(3, 4) merges {3, 4}. union(2, 3) merges sets containing 2 and 3 -> {1, 2, 3, 4}.

2. Step 2: Check element 5's set

   Element 5 was never unioned, so it remains separate.

3. Final Answer:

   Elements 1 and 4 belong to the same set -> Option A

4. Quick Check:

   1 and 4 connected; 5 separate [OK]

Hint: Only unioned elements share sets; isolated remain separate [OK]

Common Mistakes:

• Assuming all elements merge after some unions
• Thinking element 5 is connected without union
• Confusing which elements are merged