Path Compression in Union Find in DSA C - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to return the parent of element x in the Union Find structure.

DSA C

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

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

Afind(parent, parent[x])

Bfind(parent, x)

Cx

Dparent[x]

Attempts:

3 left

💡 Hint

Common Mistakes

Returning x directly without recursion.

Returning parent[x] without recursion.

The find function recursively finds the root parent of x by calling find on parent[x].

2fill in blank

medium

Complete the code to implement path compression by updating parent[x] during find.

DSA C

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

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

Ax

Bfind(parent, x)

Cparent[x]

Dfind(parent, parent[x])

Attempts:

3 left

💡 Hint

Common Mistakes

Assigning parent[x] to x directly.

Assigning parent[x] to find(parent, x) causing infinite recursion.

Path compression updates 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 roots.

DSA C

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

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

Aa

Bb

Cparent[a]

Dparent[b]

Attempts:

3 left

💡 Hint

Common Mistakes

Assigning parent[a] = a which does nothing.

Assigning parent[b] = b which does nothing.

To merge sets, assign parent of root b to root a: parent[b] = a. Fill the blank with 'a'.

4fill in blank

hard

Fill both blanks to complete the union function that merges two sets by their roots.

DSA C

void union_sets(int parent[], int a, int b) {
    a = find(parent, a);
    b = find(parent, 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

Swapping the order and assigning parent[a] = b.

Using parent[a] or parent[b] as indices.

To merge sets, assign parent of root b to root a: parent[b] = a.

5fill in blank

hard

Fill all three blanks to implement find with path compression and union that merges sets.

DSA C

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

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

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

Afind(parent, parent[x])

Bfind(parent, a)

Cfind(parent, b)

Dfind(parent, x)

Attempts:

3 left

💡 Hint

Common Mistakes

Not updating a and b in union.

Assigning parent[x] incorrectly in find.

In find, path compression assigns parent[x] to find(parent, parent[x]). In union, a and b are updated by find(parent, a) and find(parent, b) respectively.