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

Practice - 5 Tasks

1fill in blank

easy

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

DSA C

for (int i = 0; i < n; i++) {
    parent[i] = [1];
}

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

An

B0

C-1

Di

Attempts:

3 left

💡 Hint

Common Mistakes

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

Using n as parent which is out of array bounds.

Each element starts as its own parent, so parent[i] = i.

2fill in blank

medium

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

DSA C

int find(int x) {
    if (parent[x] != x) {
        parent[x] = [1];
    }
    return parent[x];
}

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

Afind(parent[x])

Bparent[parent[x]]

Cparent[x]

Dx

Attempts:

3 left

💡 Hint

Common Mistakes

Assigning parent[x] to parent[parent[x]] which may not be root.

Returning x directly without path compression.

Path compression sets parent[x] to the root found by recursively calling find on parent[x].

3fill in blank

hard

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

DSA C

void union_sets(int a, int b) {
    a = find(a);
    b = find(b);
    if (a != b) {
        parent[[1]] = [2];
    }
}

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

Aa

Bb

Cparent[a]

Dparent[b]

Attempts:

3 left

💡 Hint

Common Mistakes

Assigning parent[parent[a]] or parent[parent[b]] which is incorrect.

Assigning parent[b] = a instead of parent[a] = b.

We set the parent of root a to root b to merge sets.

4fill in blank

hard

Fill both blanks to implement union by rank optimization.

DSA C

void union_sets(int a, int b) {
    a = find(a);
    b = find(b);
    if (a != b) {
        if (rank[a] < rank[b]) {
            parent[[1]] = [2];
        } else {
            parent[b] = a;
            if (rank[a] == rank[b]) {
                rank[a]++;
            }
        }
    }
}

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

Aa

Bb

Cparent[a]

Dparent[b]

Attempts:

3 left

💡 Hint

Common Mistakes

Swapping a and b incorrectly in assignment.

Not updating rank when ranks are equal.

If rank[a] < rank[b], set parent[a] = b to attach the smaller rank tree under the larger rank tree.

5fill in blank

hard

Fill all three blanks to implement a function that checks if two elements are in the same set.

DSA C

int is_same_set(int a, int b) {
    return [1](a) == [2](b);
}

void make_set(int v) {
    parent[v] = v;
    rank[v] = [3];
}

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

Afind

Bunion_sets

C0

D1

Attempts:

3 left

💡 Hint

Common Mistakes

Using union_sets instead of find in is_same_set.

Initializing rank to 1 instead of 0.

Use find to get root parents and compare; rank is initialized to 0.