Disjoint set (Union-Find) in Data Structures Theory - Interactive Code Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize each element as its own parent in a disjoint set.

Data Structures Theory

parent = [[1] for i in range(n)]

Drag options to blanks, or click blank then click option'

Ai

B0

Cn

D-1

Attempts:

3 left

💡 Hint

Common Mistakes

Setting all parents to 0 or -1 instead of their own index.

Each element starts as its own parent, so the parent of element i is i itself.

2fill in blank

medium

Complete the code to find the root parent of an element with path compression.

Data Structures Theory

def find(x):
    if parent[x] != x:
        parent[x] = [1](parent[x])
    return parent[x]

Drag options to blanks, or click blank then click option'

Aroot

Bfind

Cunion

Dparent

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'union' instead of 'find' causes errors.

Not updating parent[x] for path compression.

The find function recursively finds the root parent and applies path compression by updating the parent.

3fill in blank

hard

Fix the error in the union function to correctly merge two sets by rank.

Data Structures Theory

def union(x, y):
    rootX = find(x)
    rootY = find(y)
    if rootX != rootY:
        if rank[rootX] < rank[rootY]:
            parent[rootX] = [1]
        elif rank[rootX] > rank[rootY]:
            parent[rootY] = rootX
        else:
            parent[rootY] = rootX
            rank[rootX] += 1

Drag options to blanks, or click blank then click option'

ArootX

By

Cx

DrootY

Attempts:

3 left

💡 Hint

Common Mistakes

Assigning parent[rootX] = rootX instead of rootY.

Mixing up which root becomes parent.

When rank of rootX is less, rootX's parent should be rootY to merge correctly.

4fill in blank

hard

Fill both blanks to create a dictionary comprehension that maps each element to its root parent.

Data Structures Theory

root_map = {element: [1](element) for element in [2]

Drag options to blanks, or click blank then click option'

Afind

Brange(n)

Clist(range(n))

Dparent

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'parent' directly instead of 'find' causes incorrect roots.

Using 'range(n)' without converting to list is acceptable but here list is expected.

This comprehension applies the find function to each element in the list of elements from 0 to n-1.

5fill in blank

hard

Fill the blanks to create a set of unique root parents from a list of elements.

Data Structures Theory

unique_roots = { [1](element) for element in [2] }

Drag options to blanks, or click blank then click option'

Afind

Belements

Celement not in unique_roots

Dparent

Attempts:

3 left

💡 Hint

Common Mistakes

Not using find causes incorrect roots.

Using 'parent' instead of 'elements' for iteration.

Adding an unnecessary condition for uniqueness.

This set comprehension collects unique root parents by applying find to each element in elements. Sets automatically remove duplicates.

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