Disjoint set (Union-Find) in Data Structures Theory - Practice Problems & Coding Challenges

Challenge - 5 Problems

🧠 Conceptual

intermediate

Understanding the purpose of Disjoint Set

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

A To sort elements in ascending order using divide and conquer

B To implement a priority queue with fast insertion and extraction

C To store key-value pairs for fast lookup

D To efficiently manage a collection of non-overlapping sets and quickly determine if two elements belong to the same set

💡 Hint

Think about grouping elements and checking their group membership efficiently.

The Disjoint Set data structure is designed to keep track of elements partitioned into disjoint sets and supports two main operations: finding which set an element belongs to and uniting two sets. It is not used for sorting, key-value storage, or priority queues.

📋 Factual

intermediate

Time complexity of Union-Find operations

What is the amortized time complexity of the find and union operations in a Disjoint Set with path compression and union by rank/size?

A O(1) amortized

B O(log n) amortized

C O(α(n)) amortized, where α is the inverse Ackermann function

D O(n) amortized

💡 Hint

The inverse Ackermann function grows extremely slowly and is practically constant for all reasonable input sizes.

With path compression and union by rank or size, both find and union operations run in nearly constant time, specifically O(α(n)), where α(n) is the inverse Ackermann function, which grows very slowly and can be considered almost constant for all practical input sizes.

🔍 Analysis

advanced

Result of union operations sequence

Given a Disjoint Set with elements {1, 2, 3, 4, 5} initially all separate, what is the number of distinct sets after performing these operations in order?

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

A 2

B 1

C 3

D 4

💡 Hint

Track how sets merge step-by-step.

Initially, there are 5 sets: {1}, {2}, {3}, {4}, {5}.
After union(1, 2): {1,2}, {3}, {4}, {5}
After union(3, 4): {1,2}, {3,4}, {5}
After union(2, 3): {1,2,3,4}, {5}
After union(5, 1): {1,2,3,4,5}
Only one set remains.

❓ Comparison

advanced

Difference between union by rank and union by size

Which statement correctly describes the difference between union by rank and union by size in Disjoint Set implementations?

A Union by rank attaches the tree with smaller height under the root of the tree with larger height, while union by size attaches the tree with fewer nodes under the root of the tree with more nodes

B Union by rank attaches the tree with fewer nodes under the root of the tree with more nodes, while union by size attaches the tree with smaller height under the root of the tree with larger height

C Union by rank always results in taller trees than union by size

D Union by rank and union by size are identical and interchangeable without any difference

💡 Hint

Consider what 'rank' and 'size' represent in the context of trees.

Union by rank uses the height (or an upper bound on height) of the tree to decide which root becomes the parent, attaching the shorter tree under the taller one. Union by size uses the number of nodes in the tree to decide, attaching the smaller tree under the larger one. They are similar but use different criteria.

❓ Reasoning

expert

Detecting cycle in an undirected graph using Disjoint Set

Consider an undirected graph with edges added one by one. How can a Disjoint Set be used to detect if adding a new edge creates a cycle?

A Check if the two vertices of the new edge belong to the same set; if yes, adding the edge creates a cycle

B Check if the two vertices of the new edge belong to different sets; if yes, adding the edge creates a cycle

C Use Disjoint Set to count the total number of edges and vertices to detect cycles

D Always add the edge without any checks; cycles cannot be detected using Disjoint Set

💡 Hint

Think about what it means if two vertices are already connected before adding an edge.

If the two vertices of the new edge are already in the same set, it means they are connected by some path. Adding the edge would create a cycle. If they are in different sets, the edge connects two separate components and does not form a cycle.

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