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.