Union Find Disjoint Set Data Structure in DSA C - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Union Find after union operations

What is the printed parent array after performing the union operations shown below on a Union Find structure of size 5?

DSA C

int parent[5];
for (int i = 0; i < 5; i++) parent[i] = i;

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

int find_set(int v) {
    if (v == parent[v]) return v;
    return find_set(parent[v]);
}

union_sets(0, 1);
union_sets(1, 2);
union_sets(3, 4);

for (int i = 0; i < 5; i++) printf("%d ", parent[i]);

A [0, 0, 1, 3, 3]

B [0, 1, 2, 3, 4]

C [0, 0, 0, 3, 3]

D [1, 1, 1, 4, 4]

💡 Hint

Remember that union_sets attaches the root of one set to the root of another. The parent array shows direct parents, not necessarily roots after path compression.

After union_sets(0,1), parent[1] = 0. After union_sets(1,2), parent[2] = 0 (since find_set(1) = 0). After union_sets(3,4), parent[4] = 3. So parent array is [0,0,0,3,3].

🧠 Conceptual

intermediate

Number of disjoint sets after unions

Given a Union Find structure initialized with 6 elements (0 to 5), after performing union(0,1), union(2,3), union(4,5), how many disjoint sets remain?

A 1

B 6

C 2

D 3

💡 Hint

Each union merges two sets into one, reducing the total count by one.

Initially, there are 6 sets. Each union merges two sets, so after 3 unions, the number of sets is 6 - 3 = 3.

🔧 Debug

advanced

Identify the bug in find_set with path compression

What error will the following find_set function cause when called repeatedly?

DSA C

int find_set(int v) {
    if (v == parent[v]) return v;
    return find_set(parent[v]);
    parent[v] = find_set(parent[v]);
}

A Parent array never updates, so no path compression

B Stack overflow due to infinite recursion

C No error, works correctly

D Compilation error due to unreachable code

💡 Hint

Check the order of statements and unreachable code after return.

The line 'parent[v] = find_set(parent[v]);' is after the return statement, so it is unreachable and never executed. This causes no path compression.

❓ Predict Output

advanced

Output of union-find with union by rank

What is the rank array after performing the following union operations on a union-find with union by rank?

DSA C

int parent[5], rank[5];
for (int i = 0; i < 5; i++) {
    parent[i] = i;
    rank[i] = 0;
}

int find_set(int v) {
    if (v == parent[v]) return v;
    return parent[v] = find_set(parent[v]);
}

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

union_sets(0, 1);
union_sets(2, 3);
union_sets(1, 2);

for (int i = 0; i < 5; i++) printf("%d ", rank[i]);

A [1, 0, 0, 0, 0]

B [2, 0, 1, 0, 0]

C [1, 1, 0, 0, 0]

D [0, 0, 0, 0, 0]

💡 Hint

Rank increases only when two sets of equal rank are united.

After union_sets(0,1), rank[0] becomes 1. union_sets(2,3) makes rank[2] = 1. union_sets(1,2) finds roots 0 (rank 1) and 2 (rank 1), equal ranks so parent[2] = 0 and rank[0]++ to 2. rank[2] remains 1. So rank array is [2, 0, 1, 0, 0].

🧠 Conceptual

expert

Maximum number of unions before all elements connected

For a Union Find structure with n elements, what is the maximum number of union operations needed to connect all elements into a single set?

A n - 1

B n

C n + 1

D 2 * n

💡 Hint

Think about how many edges connect n nodes in a tree.

To connect n elements into one set, you need exactly n-1 unions, because each union reduces the number of sets by one, starting from n sets.