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.

Practice

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

easy

A. To sort elements in ascending order

B. To efficiently track and merge groups of connected elements

C. To store key-value pairs for fast lookup

D. To implement a queue with priority

Solution

1. Step 1: Understand the role 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 priority queues serve different purposes unrelated to grouping connected components.

3. Final Answer:

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

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
• Assuming it manages priority queues

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

easy

A. int parent[n]; for(int i=0; i

B. int parent[n]; for(int i=0; i

C. int parent[n]; for(int i=0; i

D. int parent[n]; for(int i=0; i

Solution

1. Step 1: Understand initialization of Union Find

   Each element starts as its own parent, so parent[i] = i for all i from 0 to n-1.

2. Step 2: Check each option

   int parent[n]; for(int i=0; i

3. Final Answer:

   int parent[n]; for(int i=0; i -> Option A

4. Quick Check:

   Initialize parent[i] = i [OK]

Hint: Parent array starts with self indices [OK]

Common Mistakes:

• Setting all parents to zero
• Using -1 as parent without meaning
• Assigning parent to n (out of range)

3. Consider the following C code using Union Find for 5 elements (0 to 4):

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

// Union operations
union_set(parent, 0, 1);
union_set(parent, 1, 2);
union_set(parent, 3, 4);

// Find operations
int a = find_set(parent, 2);
int b = find_set(parent, 4);

printf("%d %d", a, b);

Assuming union_set merges sets and find_set returns the root parent, what is the printed output?

medium

A. 0 3

B. 1 3

C. 2 4

D. 0 4

Solution

1. Step 1: Trace union operations

   Initially, parent[i] = i for i=0..4.
   union_set(0,1) merges sets containing 0 and 1, root becomes 0.
   union_set(1,2) merges sets containing 1 and 2, root is 0 (since 1's root is 0).
   union_set(3,4) merges sets containing 3 and 4, root becomes 3.

2. Step 2: Trace find operations

   find_set(2) returns root of 2, which is 0.
   find_set(4) returns root of 4, which is 3.

3. Final Answer:

   0 3 -> Option A

4. Quick Check:

   Roots after unions: 2->0, 4->3 [OK]

Hint: Follow union roots to find final parents [OK]

Common Mistakes:

• Assuming find_set returns the element itself
• Not updating roots after unions
• Mixing up which element is root

4. The following C code attempts to implement union_set but has a bug:

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

What is the bug in this code?

medium

A. It should assign parent[rootB] = rootA instead

B. It does not check if rootA equals rootB before union

C. It assigns parent[a] instead of parent[rootA], breaking the set structure

D. It uses find_set incorrectly by passing wrong parameters

Solution

1. Step 1: Analyze union assignment

   The union should link the root of one set to the root of the other.
   Assigning parent[a] = rootB is wrong because 'a' may not be a root.

2. Step 2: Correct union assignment

   It should assign parent[rootA] = rootB to merge sets properly.
   This maintains the tree structure of the disjoint sets.

3. Final Answer:

   It assigns parent[a] instead of parent[rootA], breaking the set structure -> Option C

4. Quick Check:

   Union must link roots, not elements [OK]

Hint: Always link root parents in union [OK]

Common Mistakes:

• Assigning parent of non-root element
• Skipping root equality check
• Confusing parameters in find_set

5. You have 7 elements (0 to 6) initially separate. After these union operations:

union_set(parent, 0, 1);
union_set(parent, 1, 2);
union_set(parent, 3, 4);
union_set(parent, 5, 6);
union_set(parent, 2, 5);

How many distinct sets remain?

hard

A. 5

B. 4

C. 3

D. 2

Solution

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

   Initially: 7 sets: {0}, {1}, {2}, {3}, {4}, {5}, {6}
   union(0,1): {0,1}, {2}, {3}, {4}, {5}, {6}
   union(1,2): {0,1,2}, {3}, {4}, {5}, {6}
   union(3,4): {0,1,2}, {3,4}, {5}, {6}
   union(5,6): {0,1,2}, {3,4}, {5,6}
   union(2,5): merges sets {0,1,2} and {5,6} into {0,1,2,5,6}, {3,4}

2. Step 2: Count remaining sets

   Remaining sets are {0,1,2,5,6} and {3,4}.
   Total distinct sets = 2.

3. Final Answer:

   2 -> Option D

4. Quick Check:

   Count sets after unions = 2 [OK]

Hint: Count merged groups carefully after each union [OK]

Common Mistakes:

• Forgetting last union merges two sets
• Counting elements instead of sets
• Assuming all unions merge all sets