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.