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                 |
  [Compare roots] -- Same? -- Yes --> [Already connected, do nothing]
               |
              No
               |
               v
  [Union sets by linking roots]
               |
               v
  [Update parent pointers]
               |
               v
           [Done]

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

Execution Sample

DSA C++

parent = [0,1,2,3]
find(2)
union(1,2)
find(2)

Initialize sets, find root of 2, union sets containing 1 and 2, then find root of 2 again.

Execution Table

Step	Operation	Nodes in Sets	Pointer Changes	Visual State
1	Initialize parent array	[0], [1], [2], [3]	parent = [0,1,2,3]	┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐ │ data:0 │ │ data:1 │ │ data:2 │ │ data:3 │ │ parent:0│ │ parent:1│ │ parent:2│ │ parent:3│ └────────┘ └────────┘ └────────┘ └────────┘
2	find(2)	[0], [1], [2], [3]	root of 2 is 2	No pointer changes Root of 2 is 2
3	union(1,2)	[0], [1,2], [3]	parent[2] = 1	Before: ┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐ │ data:0 │ │ data:1 │ │ data:2 │ │ data:3 │ │ parent:0│ │ parent:1│ │ parent:2│ │ parent:3│ └────────┘ └────────┘ └────────┘ └────────┘ Step: parent[2] points to 1 After: ┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐ │ data:0 │ │ data:1 │ │ data:2 │ │ data:3 │ │ parent:0│ │ parent:1│ │ parent:1│ │ parent:3│ └────────┘ └────────┘ └────────┘ └────────┘
4	find(2)	[0], [1,2], [3]	root of 2 is 1	Traverse: 2 -> parent 1 Root of 2 is 1
5	union(0,3)	[0,3], [1,2]	parent[3] = 0	Before: ┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐ │ data:0 │ │ data:1 │ │ data:2 │ │ data:3 │ │ parent:0│ │ parent:1│ │ parent:1│ │ parent:3│ └────────┘ └────────┘ └────────┘ └────────┘ Step: parent[3] points to 0 After: ┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐ │ data:0 │ │ data:1 │ │ data:2 │ │ data:3 │ │ parent:0│ │ parent:1│ │ parent:1│ │ parent:0│ └────────┘ └────────┘ └────────┘ └────────┘
6	find(3)	[0,3], [1,2]	root of 3 is 0	Traverse: 3 -> parent 0 Root of 3 is 0
7	union(2,3)	[0,1,2,3]	parent[1] = 0	Before: ┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐ │ data:0 │ │ data:1 │ │ data:2 │ │ data:3 │ │ parent:0│ │ parent:1│ │ parent:1│ │ parent:0│ └────────┘ └────────┘ └────────┘ └────────┘ Find roots: 2->1, 3->0 Link root 1 to root 0 After: ┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐ │ data:0 │ │ data:1 │ │ data:2 │ │ data:3 │ │ parent:0│ │ parent:0│ │ parent:1│ │ parent:0│ └────────┘ └────────┘ └────────┘ └────────┘
8	find(2)	[0,1,2,3]	root of 2 is 0	Traverse: 2 -> 1 -> 0 Root of 2 is 0
9	End	All elements connected	No pointer changes	All nodes share root 0

💡 All elements connected or no further unions possible

Variable Tracker

Variable	Start	After Step 3	After Step 5	After Step 7	Final
parent	[0,1,2,3]	[0,1,1,3]	[0,1,1,0]	[0,0,1,0]	[0,0,1,0]

Key Moments - 3 Insights

Why does find(2) return 1 after union(1,2) instead of 2?

After union(1,2) at step 3, parent[2] points to 1, so find(2) follows parent to 1 (see step 4).

Why do we link root of one set to root of another during union?

Linking roots merges sets without breaking existing connections, as shown in step 7 where root 1 points to root 0.

What happens if we call find on an element whose parent is itself?

It means the element is the root of its set, so find returns the element itself, as in step 2 for element 2.

Visual Quiz - 3 Questions

Look at the execution table at step 4, what is the root of element 2?

A 2

B 1

C 0

D 3

💡 Hint

Check the 'Operation' and 'Visual State' columns at step 4 in execution_table.

At which step does element 3's parent change to 0?

A Step 5

B Step 7

C Step 3

D Step 2

💡 Hint

Look for 'parent[3] = 0' in the 'Pointer Changes' column.

If we call find(3) after step 7, what is the root returned?

A 3

B 1

C 0

D 2

💡 Hint

See step 8 traversal: 3 -> 0 root.

Concept Snapshot

Union Find DS:
- Each element starts as its own parent.
- find(x): follow parent links to root.
- union(a,b): link roots if different.
- Efficient for checking connected components.
- Parent array stores links; roots point to themselves.

Full Transcript

Union Find Disjoint Set Data Structure starts by initializing each element as its own set with itself as parent. The find operation follows parent pointers until it reaches the root, which is an element that points to itself. The union operation merges two sets by linking the root of one set to the root of the other, effectively combining them. This process is shown step-by-step with parent array updates and pointer changes. Key moments include understanding why find returns the root, how union links roots, and what it means when an element is its own parent. The visual quiz tests understanding of root finding and parent updates. This data structure is useful for efficiently managing disjoint sets and checking connectivity.

Practice

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

easy

A. To efficiently track and merge groups of connected elements

B. To sort elements in ascending order

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 can merge.

2. Step 2: Compare with other data structures

   Sorting elements, storing key-value pairs, or implementing priority queues are different tasks handled by other data structures.

3. Final Answer:

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

4. Quick Check:

   Union Find = Track and merge groups [OK]

Hint: Union Find = track connected groups fast [OK]

Common Mistakes:

• Confusing Union Find with sorting algorithms
• Thinking it stores key-value pairs like a map
• Assuming it manages priority like a heap

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

easy

A. int parent[n+1]; for(int i=1; i<=n; i++) parent[i] = i;

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

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

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

Solution

1. Step 1: Initialize parent array correctly

   The parent array should have size n, and each element should initially be its own parent, so indices 0 to n-1 must be set.

2. Step 2: Check loop boundaries

   Loop must run from 0 to n-1 (i < n) to avoid out-of-bounds errors.

3. Final Answer:

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

4. Quick Check:

   Initialize parents from 0 to n-1 [OK]

Hint: Initialize parents from 0 to n-1 [OK]

Common Mistakes:

• Using <= n causing out-of-bounds error
• Starting loop from 1 when array is 0-indexed
• Declaring array size incorrectly

3. Consider the following C++ code using Union Find:

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

// Union function
void unionSet(int a, int b) {
  int rootA = findSet(a);
  int rootB = findSet(b);
  if(rootA != rootB) parent[rootB] = rootA;
}

// Find function
int findSet(int x) {
  if(parent[x] == x) return x;
  return parent[x] = findSet(parent[x]);
}

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

cout << (findSet(2) == findSet(0)) << " " << (findSet(4) == findSet(0));

What is the output?

medium

A. 0 0

B. 0 1

C. 1 1

D. 1 0

Solution

1. Step 1: Perform unions and find roots

   unionSet(0,1) merges sets of 0 and 1; unionSet(1,2) merges sets of 1 and 2, so 0,1,2 are connected. unionSet(3,4) connects 3 and 4.

2. Step 2: Check if 2 and 0 share the same root, and if 4 and 0 share the same root

   findSet(2) == findSet(0) is true (1), findSet(4) == findSet(0) is false (0).

3. Final Answer:

   1 0 -> Option D

4. Quick Check:

   Connected(2,0) = 1, Connected(4,0) = 0 [OK]

Hint: Check connected sets after unions [OK]

Common Mistakes:

• Assuming 4 is connected to 0
• Forgetting path compression in findSet
• Mixing up union order

4. The following code snippet for Union Find has a bug. What is the error?

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

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

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

unionSet(0, 1);
unionSet(1, 2);
cout << (findSet(2) == findSet(0));

medium

A. Incorrect initialization of parent array

B. Union function does not check if roots are equal

C. Missing path compression in findSet function

D. Array size is too small for elements

Solution

1. Step 1: Analyze findSet function

   The findSet function recursively finds the root but does not update parent[x] to root, missing path compression optimization.

2. Step 2: Understand impact of missing path compression

   Without path compression, findSet is slower on deep trees but still correct. Other options are incorrect because initialization and union checks are correct, and array size matches elements.

3. Final Answer:

   Missing path compression in findSet function -> Option C

4. Quick Check:

   findSet lacks path compression [OK]

Hint: Check if findSet updates parent for path compression [OK]

Common Mistakes:

• Thinking union lacks root equality check
• Assuming parent array is wrongly initialized
• Confusing array size with element count

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

unionSet(0, 1);
unionSet(2, 3);
unionSet(4, 5);
unionSet(1, 2);
unionSet(0, 4);

How many distinct sets remain?

hard

A. 1

B. 2

C. 3

D. 4

Solution

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

   Initially: {0}, {1}, {2}, {3}, {4}, {5} unionSet(0,1) -> {0,1}, {2}, {3}, {4}, {5} unionSet(2,3) -> {0,1}, {2,3}, {4}, {5} unionSet(4,5) -> {0,1}, {2,3}, {4,5} unionSet(1,2) merges {0,1} and {2,3} -> {0,1,2,3}, {4,5} unionSet(0,4) merges {0,1,2,3} and {4,5} -> {0,1,2,3,4,5}

2. Step 2: Count remaining distinct sets

   All elements are connected in one set after last union.

3. Final Answer:

   1 -> Option A

4. Quick Check:

   All merged into one set [OK]

Hint: Count merges to find final distinct sets [OK]

Common Mistakes:

• Counting sets before all unions
• Not merging transitive connections
• Assuming unions only connect pairs