Union Find Disjoint Set Data Structure in DSA Python - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize the parent array where each element is its own parent.

DSA Python

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

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

Alen(parent)

B0

C1

Dn

Attempts:

3 left

💡 Hint

Common Mistakes

Using 0 or 1 instead of the number of elements for range.

Using length of parent before it is defined.

We create a list where each element is its own parent, so we use the size 'n' to range over all elements.

2fill in blank

medium

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

DSA Python

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'

Aunion

Bfind

Cparent

Dx

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'union' instead of 'find' inside the function.

Assigning parent[x] to x directly without recursion.

The find function calls itself recursively to find the root parent and compresses the path by updating parent[x].

3fill in blank

hard

Fix the error in the union function to correctly merge two sets by their root parents.

DSA Python

def union(a, b):
    rootA = find(a)
    rootB = find(b)
    if rootA != rootB:
        parent[[1]] = rootB

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

ArootA

Ba

Cb

DrootB

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'a' or 'b' instead of their root parents.

Assigning parent of rootB instead of rootA.

We assign the parent of rootA to rootB to merge the two sets correctly.

4fill in blank

hard

Fill both blanks to check if two elements are in the same set.

DSA Python

def connected(x, y):
    return find([1]) == find([2])

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

Ax

By

Cparent

Droot

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'parent' or 'root' instead of the elements.

Comparing elements directly without finding their roots.

We check if the root parents of x and y are the same to determine if they are connected.

5fill in blank

hard

Fill all three blanks to implement union by rank optimization.

DSA Python

def union(a, b):
    rootA = find(a)
    rootB = find(b)
    if rootA != rootB:
        if rank[rootA] < [1]:
            parent[rootA] = rootB
        elif rank[rootA] > [2]:
            parent[rootB] = rootA
        else:
            parent[rootB] = rootA
            rank[rootA] += [3]

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

Arank[rootB]

Brank[rootA]

C1

Drank[a]

Attempts:

3 left

💡 Hint

Common Mistakes

Comparing rank[rootA] with rank[rootA] instead of rank[rootB].

Increasing rank by a value other than 1.

Using rank[a] instead of rank[rootB].

We compare rank[rootA] with rank[rootB] to decide which root becomes parent, and increase rank by 1 when ranks are equal.

Practice

1. What is the main purpose of the Union Find Disjoint Set data structure?

easy

A. To efficiently track and merge groups of connected elements

B. To sort elements in ascending order

C. To store key-value pairs for fast lookup

D. To implement a queue with fast enqueue and dequeue

Solution

1. Step 1: Understand the purpose of Union Find

   The Union Find data structure is designed to keep track of which elements belong to which groups or sets, especially when these groups merge.

2. Step 2: Compare with other data structures

   Sorting, key-value storage, and queue operations are unrelated to Union Find's main goal.

3. Final Answer:

   To efficiently track and merge groups of connected elements -> Option A

4. Quick Check:

   Union Find = track and merge groups [OK]

Hint: Union Find = manage connected groups fast [OK]

Common Mistakes:

• Confusing Union Find with sorting algorithms
• Thinking it stores key-value pairs
• Mixing it up with queue or stack data structures

2. Which of the following is the correct way to initialize a Union Find parent array for 5 elements in Python?

easy

A. parent = [None] * 5

B. parent = [1, 1, 1, 1, 1]

C. parent = [5, 5, 5, 5, 5]

D. parent = [0, 1, 2, 3, 4]

Solution

1. Step 1: Understand initialization of Union Find

   Each element starts as its own parent, so the parent array should have each index equal to itself.

2. Step 2: Check each option

   parent = [0, 1, 2, 3, 4] correctly sets parent[i] = i for i in 0 to 4. Others do not represent this.

3. Final Answer:

   parent = [0, 1, 2, 3, 4] -> Option D

4. Quick Check:

   Parent array init = self indices [OK]

Hint: Parent array starts with self indices [OK]

Common Mistakes:

• Setting all parents to 1 or a fixed number
• Using None which breaks find operations
• Confusing size array with parent array

3. What is the output of the following code?

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    def union(self, a, b):
        rootA = self.find(a)
        rootB = self.find(b)
        if rootA != rootB:
            self.parent[rootB] = rootA

uf = UnionFind(4)
uf.union(0, 1)
uf.union(2, 3)
uf.union(1, 3)
print(uf.parent)

medium

A. [0, 0, 0, 2]

B. [0, 0, 0, 0]

C. [0, 0, 2, 2]

D. [0, 1, 2, 3]

Solution

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

   Init: [0,1,2,3]
   Union(0,1): find(0)=0, find(1)=1 -> parent[1]=0 -> [0,0,2,3]
   Union(2,3): find(2)=2, find(3)=3 -> parent[3]=2 -> [0,0,2,2]
   Union(1,3): find(1)=0, find(3)=2 (sets parent[3]=2) -> parent[2]=0 -> [0,0,0,2]

2. Step 2: Verify print output

   No additional find calls before print. parent[3] points to 2 (now root 0), but not fully compressed to 0. Output: [0, 0, 0, 2]

3. Final Answer:

   [0, 0, 0, 2] -> Option A

4. Quick Check:

   parent = [0,0,0,2] after partial compression [OK]

Hint: Trace find calls and compression timing during union [OK]

Common Mistakes:

• Forgetting last union sets parent[2]=0 -> [0,0,2,2]
• Over-applying path compression -> [0,0,0,0]
• Ignoring unions entirely

4. Identify the bug in this Union Find union method:

def union(self, a, b):
    rootA = self.find(a)
    rootB = self.find(b)
    if rootA != rootB:
        self.parent[rootA] = rootB

medium

A. The find method is not called correctly

B. It should assign parent of rootB to rootA, not the other way

C. The if condition should be rootA == rootB

D. The method is missing a return statement

Solution

1. Step 1: Understand union direction

   Union should attach one root to the other to merge sets. Usually, parent of rootB is set to rootA or vice versa consistently.

2. Step 2: Check given code

   Code sets parent[rootA] = rootB, which reverses the usual convention and can cause incorrect tree structure or confusion.

3. Final Answer:

   It should assign parent of rootB to rootA, not the other way -> Option B

4. Quick Check:

   Union sets parent[rootB] = rootA [OK]

Hint: Union sets parent of second root to first root [OK]

Common Mistakes:

• Swapping roots incorrectly in union
• Not calling find before union
• Confusing equality check in if condition

5. Given a graph with 6 nodes and edges [(0,1), (1,2), (3,4)], how many connected components does the Union Find structure report after union operations on these edges?

hard

A. 4

B. 2

C. 3

D. 5

Solution

1. Step 1: Initialize 6 separate nodes

   Initially, each node is its own component: 6 components total.

2. Step 2: Perform unions for edges

   Union(0,1) merges nodes 0 and 1 -> components reduce to 5.
   Union(1,2) merges node 2 with 0-1 group -> components reduce to 4.
   Union(3,4) merges nodes 3 and 4 -> components reduce to 3.

3. Step 3: Count remaining components

   Node 5 remains alone -> total components = 3.

4. Final Answer:

   3 -> Option C

5. Quick Check:

   6 nodes - 3 unions = 3 components [OK]

Hint: Components = nodes - unions done [OK]

Common Mistakes:

• Counting edges instead of components
• Forgetting isolated nodes count as components
• Miscounting after unions