Union Find Disjoint Set Data Structure in DSA C

Mental Model

Union Find keeps track of groups of connected items by linking them under a single leader. It helps quickly find if two items belong to the same group.

Analogy: Imagine a classroom where students form friend groups. Each group has a leader. If two students are friends, they share the same leader. Union Find helps find the leader of any student and join two groups by choosing one leader.

0 1 2 3 4 5 6 7 8 9
↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑
Each number is alone, leader points to itself:
0 -> 0
1 -> 1
2 -> 2
3 -> 3
4 -> 4
5 -> 5
6 -> 6
7 -> 7
8 -> 8
9 -> 9

Dry Run Walkthrough

Input: Start with 5 elements: 0,1,2,3,4 all separate. Perform union(0,1), union(1,2), union(3,4), then check if 0 and 2 are connected.

Goal: Show how union merges groups and find checks if two elements share the same leader.

Step 1: Initialize each element as its own leader

0 -> 0
1 -> 1
2 -> 2
3 -> 3
4 -> 4

Why: Start with all elements separate, each is leader of itself

Step 2: Union 0 and 1: make leader of 1 point to leader of 0

0 -> 0
1 -> 0
2 -> 2
3 -> 3
4 -> 4

Why: Connect 0 and 1 by linking 1 under 0's leader

Step 3: Union 1 and 2: find leaders of 1 and 2, link leader of 2 to leader of 0

0 -> 0
1 -> 0
2 -> 0
3 -> 3
4 -> 4

Why: 2 joins the group led by 0 through 1

Step 4: Union 3 and 4: make leader of 4 point to leader of 3

0 -> 0
1 -> 0
2 -> 0
3 -> 3
4 -> 3

Why: Connect 3 and 4 as a separate group

Step 5: Find if 0 and 2 are connected: find leaders of both

0 -> 0
1 -> 0
2 -> 0
3 -> 3
4 -> 3

Why: Both 0 and 2 have leader 0, so they are connected

Result:

0 -> 0
1 -> 0
2 -> 0
3 -> 3
4 -> 3
Answer: 0 and 2 are connected (same leader)

Annotated Code

DSA C

#include <stdio.h>
#include <stdlib.h>

#define SIZE 5

int parent[SIZE];

// Find leader of element x with path compression
int find(int x) {
    if (parent[x] != x) {
        parent[x] = find(parent[x]); // path compression
    }
    return parent[x];
}

// Union two sets by linking leaders
void union_sets(int a, int b) {
    int leaderA = find(a);
    int leaderB = find(b);
    if (leaderA != leaderB) {
        parent[leaderB] = leaderA; // link leaderB under leaderA
    }
}

int main() {
    // Initialize each element as its own leader
    for (int i = 0; i < SIZE; i++) {
        parent[i] = i;
    }

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

    // Check if 0 and 2 are connected
    if (find(0) == find(2)) {
        printf("0 and 2 are connected\n");
    } else {
        printf("0 and 2 are NOT connected\n");
    }

    // Print parent array to show structure
    printf("Parent array:\n");
    for (int i = 0; i < SIZE; i++) {
        printf("%d -> %d\n", i, parent[i]);
    }

    return 0;
}

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

Recursively find leader and compress path for faster future lookups

int leaderA = find(a); int leaderB = find(b);

Find leaders of both elements before union

if (leaderA != leaderB) { parent[leaderB] = leaderA; }

Link one leader under the other to merge sets

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

Initialize each element as its own leader

Output

0 and 2 are connected

Parent array:

0 -> 0

1 -> 0

2 -> 0

3 -> 3

4 -> 3

Complexity Analysis

Time: O(α(n)) per operation, where α is inverse Ackermann function, almost constant because path compression flattens trees

Space: O(n) for storing parent array of size n

vs Alternative: Naive union without path compression can be O(n) per find, so this is much faster for many operations

Edge Cases

Union on elements already in the same set

No change occurs because leaders are same, avoiding cycles

DSA C

if (leaderA != leaderB) { parent[leaderB] = leaderA; }

Find on element that is its own leader

Returns element itself immediately, no recursion

DSA C

if (parent[x] != x) { ... }

Union on invalid element index (out of range)

Undefined behavior, code assumes valid input

DSA C

No explicit guard; input must be valid

When to Use This Pattern

When a problem asks to group items and quickly check if two items belong to the same group, use Union Find because it efficiently merges and finds group leaders.

Common Mistakes

Mistake: Not using path compression in find, causing slow repeated lookups
Fix: Add path compression by setting parent[x] = find(parent[x]) during find

Mistake: Linking leaders incorrectly causing cycles or wrong groups
Fix: Always link leader of one set to leader of the other after finding leaders

Summary

It keeps track of connected groups by linking elements under a single leader.

Use it when you need to quickly merge groups and check if two elements are connected.

The key is to find leaders and link them, using path compression to speed up future lookups.

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