Union Find Disjoint Set Data Structure in DSA C - Execution Trace

Concept Flow - Union Find Disjoint Set Data Structure

  [Initialize each element as its own set]
            |
            v
  [Find root of element A] ←─────┐
            |                   |
            v                   |
  [Find root of element B]      |
            |                   |
            v                   |
  [Are roots different?] --No--> [Stop]
            |
           Yes
            |
            v
  [Union sets by linking roots]
            |
            v
  [Update parent pointer]
            |
            v
          [Done]

Start with each element alone. To union, find roots of both sets. If different, link one root to the other. This merges sets.

Execution Sample

DSA C

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

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

This code finds the root of a set with path compression and unions two sets by linking roots.

Execution Table

Step	Operation	Nodes in Sets	Pointer Changes	Visual State
1	Initialize sets for elements 1,2,3,4	1,2,3,4 each alone	parent[1]=1, parent[2]=2, parent[3]=3, parent[4]=4	┌──────┐ ┌──────┐ ┌──────┐ ┌──────┐ │ 1 │ │ 2 │ │ 3 │ │ 4 │ │ next:│ │ next:│ │ next:│ │ next:│ │ 1 │ │ 2 │ │ 3 │ │ 4 │ └──────┘ └──────┘ └──────┘ └──────┘
2	Union(1, 2): find roots	1,2,3,4 each alone	find(1)=1, find(2)=2	Same as step 1
3	Union(1, 2): link root 2 to root 1	Sets: {1,2}, {3}, {4}	parent[2] = 1	┌──────┐ ┌──────┐ ┌──────┐ ┌──────┐ │ 1 │ ──→│ 2 │ │ 3 │ │ 4 │ │ next:│ │ next:│ │ next:│ │ next:│ │ 1 │ │ 1 │ │ 3 │ │ 4 │ └──────┘ └──────┘ └──────┘ └──────┘
4	Union(3, 4): find roots	Sets: {1,2}, {3}, {4}	find(3)=3, find(4)=4	Same as step 3
5	Union(3, 4): link root 4 to root 3	Sets: {1,2}, {3,4}	parent[4] = 3	┌──────┐ ┌──────┐ ┌──────┐ ┌──────┐ │ 1 │ ──→│ 2 │ │ 3 │ ──→│ 4 │ │ next:│ │ 1 │ │ next:│ │ 3 │ │ 1 │ └──────┘ └──────┘ └──────┘ └──────┘
6	Union(2, 3): find roots with path compression	Sets: {1,2}, {3,4}	find(2): parent[2]=1, find(1)=1 find(3)=3	Same as step 5
7	Union(2, 3): link root 3 to root 1	Sets: {1,2,3,4}	parent[3] = 1	┌──────┐ ┌──────┐ ┌──────┐ ┌──────┐ │ 1 │ ──→│ 2 │ │ 3 │ │ 4 │ │ next:│ │ 1 │ │ next:│ │ next:│ │ 1 │ └──────┘ │ 1 │ │ 3 │ └──────┘ └──────┘ └──────┘
8	Find(4): path compression updates parent[4]	Sets: {1,2,3,4}	find(4): parent[4]=3, find(3)=1, update parent[4]=1	┌──────┐ ┌──────┐ ┌──────┐ ┌──────┐ │ 1 │ ──→│ 2 │ │ 3 │ │ 4 │ │ next:│ │ 1 │ │ next:│ │ next:│ │ 1 │ └──────┘ │ 1 │ │ 1 │ └──────┘ └──────┘ └──────┘
9	Find(4) again: direct parent is 1	Sets: {1,2,3,4}	find(4)=1	Same as step 8
10	Stop: all elements connected in one set	Sets: {1,2,3,4}	No pointer changes	Same as step 9

💡 All elements connected in one set; no further unions needed.

Variable Tracker

Variable	Start	After 1	After 2	After 3	After 4	After 5	After 6	After 7	After 8	Final
parent[1]	1	1	1	1	1	1	1	1	1	1
parent[2]	2	2	1	1	1	1	1	1	1	1
parent[3]	3	3	3	3	3	3	3	1	1	1
parent[4]	4	4	4	4	3	3	3	3	1	1

Key Moments - 3 Insights

Why do we update parent pointers during find (path compression)?

Updating parent pointers during find (see step 8 in execution_table) flattens the tree, making future finds faster by pointing nodes directly to the root.

What happens if we try to union two elements already in the same set?

If roots are the same (step 6 shows roots 1 and 3 differ, but if same, union stops), no pointer changes occur because they are already connected.

Why do we link one root to another instead of merging all nodes directly?

Linking roots (step 3, 5, 7) keeps the structure simple and efficient, avoiding complex pointer updates for all nodes.

Visual Quiz - 3 Questions

Look at the execution_table at step 3, which parent pointer changes?

A parent[3] = 1

B parent[1] = 2

C parent[2] = 1

D parent[4] = 3

💡 Hint

Check the 'Pointer Changes' column in step 3 of execution_table.

At which step does element 4's parent pointer first change?

A Step 7

B Step 5

C Step 8

D Step 3

💡 Hint

Look at 'Pointer Changes' and 'Visual State' columns for parent[4] updates.

If we skip path compression in find, how would the variable_tracker change after step 8?

A parent[4] would remain 3

B parent[4] would be 1

C parent[3] would change to 4

D parent[2] would change to 3

💡 Hint

Check how path compression updates parent[4] in step 8 in variable_tracker.

Concept Snapshot

Union Find Disjoint Set:
- Each element starts as its own set (parent points to itself).
- find(x) returns root parent with path compression.
- union(a,b) links roots if different.
- Path compression flattens tree for fast future finds.
- Efficient for connectivity queries and merges.

Full Transcript

Union Find Disjoint Set Data Structure starts by making each element its own set with parent pointers to itself. To union two elements, we find their root parents using the find function, which also compresses paths by updating parent pointers directly to the root. If roots differ, union links one root to the other, merging sets. This process is efficient for checking connectivity and merging sets. The execution trace shows initialization, unions of pairs, and path compression updating parent pointers to flatten the structure for faster future queries.

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