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

Concept Flow - Union Find Disjoint Set Data Structure

Initialize each element as its own set

↓

Find operation: Find root of element

↓

Union operation: Merge two sets

↓

Update parent pointers

↓

Repeat for queries

↓

Check if two elements are in same set

Start with each element alone. Use Find to get root parent. Use Union to join sets by updating parents. Repeat to manage groups.

Execution Sample

DSA Go

parent := []int{0,1,2,3,4}
find := func(x int) int {
  if parent[x] != x {
    parent[x] = find(parent[x])
  }
  return parent[x]
}
union := func(a, b int) {
  parent[find(a)] = find(b)
}

Initialize sets, find root parent with path compression, union sets by linking roots.

Execution Table

Step	Operation	Nodes in Sets	Pointer Changes	Visual State
1	Initialize sets	0,1,2,3,4 each alone	parent[i] = i for i=0..4	┌────┐ ┌────┐ ┌────┐ ┌────┐ ┌────┐ │ 0 │ │ 1 │ │ 2 │ │ 3 │ │ 4 │ │ p:0 │ │ p:1 │ │ p:2 │ │ p:3 │ │ p:4 │ └────┘ └────┘ └────┘ └────┘ └────┘
2	Union(0,1)	{0,1}, {2}, {3}, {4}	parent[find(0)] = find(1) → parent[0] = 1	┌────┐ ┌────┐ ┌────┐ ┌────┐ ┌────┐ │ 0 │ │ 1 │ │ 2 │ │ 3 │ │ 4 │ │ p:1 │ │ p:1 │ │ p:2 │ │ p:3 │ │ p:4 │ └────┘ └────┘ └────┘ └────┘ └────┘ ↑ head of set {0,1}
3	Union(3,4)	{0,1}, {2}, {3,4}	parent[find(3)] = find(4) → parent[3] = 4	┌────┐ ┌────┐ ┌────┐ ┌────┐ ┌────┐ │ 0 │ │ 1 │ │ 2 │ │ 3 │ │ 4 │ │ p:1 │ │ p:1 │ │ p:2 │ │ p:4 │ │ p:4 │ └────┘ └────┘ └────┘ └────┘ └────┘ ↑ head of set {3,4}
4	Union(1,4)	Sets: {0,1,3,4}, {2}	parent[find(1)] = find(4) → parent[1] = 4	┌────┐ ┌────┐ ┌────┐ ┌────┐ ┌────┐ │ 0 │ │ 1 │ │ 2 │ │ 3 │ │ 4 │ │ p:1 │ │ p:4 │ │ p:2 │ │ p:4 │ │ p:4 │ └────┘ └────┘ └────┘ └────┘ └────┘ 0→1→4 is root, set {0,1,3,4}
5	Find(0)	Sets unchanged	Path compression: parent[0] updated to 4	┌────┐ ┌────┐ ┌────┐ ┌────┐ ┌────┐ │ 0 │ │ 1 │ │ 2 │ │ 3 │ │ 4 │ │ p:4 │ │ p:4 │ │ p:2 │ │ p:4 │ │ p:4 │ └────┘ └────┘ └────┘ └────┘ └────┘ 0 directly points to root 4
6	Find(2)	Sets unchanged	No change, parent[2] = 2	┌────┐ ┌────┐ ┌────┐ ┌────┐ ┌────┐ │ 0 │ │ 1 │ │ 2 │ │ 3 │ │ 4 │ │ p:4 │ │ p:4 │ │ p:2 │ │ p:4 │ │ p:4 │ └────┘ └────┘ └────┘ └────┘ └────┘ 2 is root of its own set
7	Check if 0 and 3 connected	Sets unchanged	Find(0)=4, Find(3)=4 → same root	Connected: Yes, both in set with root 4
8	Check if 2 and 4 connected	Sets unchanged	Find(2)=2, Find(4)=4 → different roots	Connected: No, different sets
9	Exit	All operations done	No changes	Final sets: {0,1,3,4}, {2}

💡 All union/find operations completed, sets stabilized

Variable Tracker

Variable	Start	After 1	After 2	After 3	After 4	After 5	After 6	Final
parent	[0,1,2,3,4]	[1,1,2,3,4]	[1,1,2,4,4]	[1,4,2,4,4]	[4,4,2,4,4]	[4,4,2,4,4]	[4,4,2,4,4]	[4,4,2,4,4]

Key Moments - 3 Insights

Why does the parent of 0 change from 1 to 4 after Find(0)?

During Find(0) (step 5), path compression updates parent[0] directly to root 4 for faster future lookups, as shown in execution_table row 5.

Why do we set parent[find(a)] = find(b) in union instead of just parent[a] = b?

We must link the root parents of sets to merge entire sets, not just single elements. This is shown in steps 2, 3, and 4 where parent of root nodes changes.

How do we know if two elements are in the same set?

By comparing their root parents found via Find. If roots match (step 7), they are connected; if not (step 8), they are separate.

Visual Quiz - 3 Questions

Look at the execution_table at step 4, what is the parent of node 1?

A 1

B 4

C 0

D 3

💡 Hint

Check Pointer Changes column in step 4 where parent[1] is updated

At which step does node 0's parent change directly to 4?

A Step 2

B Step 4

C Step 5

D Step 6

💡 Hint

Look at step 5 in execution_table under Pointer Changes and Visual State

If we call union(2,4) after step 6, what will be the parent of node 2?

A 4

B 2

C 1

D 0

💡 Hint

Union links root of 2 to root of 4, so parent of 2 becomes 4

Concept Snapshot

Union Find DS manages groups by linking elements to root parents.
Find(x) returns root with path compression for speed.
Union(a,b) links roots to merge sets.
Check connectivity by comparing roots.
Efficient for dynamic connectivity queries.

Full Transcript

Union Find Disjoint Set Data Structure starts by making each element its own set. The Find operation finds the root parent of an element, compressing paths for efficiency. The Union operation merges two sets by linking their root parents. This process updates parent pointers to maintain groupings. By comparing root parents, we check if two elements belong to the same set. The execution trace shows step-by-step how parents change and sets merge, with path compression optimizing future finds.

Practice

1. What is the main 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 fast enqueue and dequeue

Solution

1. Step 1: Understand the role of Union Find

   The Union Find data structure helps keep track of which elements belong to the same group or set.

2. Step 2: Identify its main operation

   It supports merging two groups and checking if two elements are in the same group efficiently.

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 manages connected groups fast [OK]

Common Mistakes:

• Confusing Union Find with sorting algorithms
• Thinking it stores key-value pairs
• Mixing it up with queue or stack data structures

2. Which of the following is the correct way to declare a Union Find parent array in Go for 5 elements?

easy

A. parent := make([]int, 5)

B. parent := [5]int{0}

C. parent := []int{5}

D. parent := make(int, 5)

Solution

1. Step 1: Understand Go slice creation

   To create a slice of integers with length 5, use make([]int, 5).

2. Step 2: Check each option

   parent := make([]int, 5) correctly uses make with []int and size 5. parent := [5]int{0} is an array but initializes only first element. parent := []int{5} creates a slice with one element 5, not length 5. parent := make(int, 5) is invalid syntax.

3. Final Answer:

   parent := make([]int, 5) -> Option A

4. Quick Check:

   Go slice with make([]int, 5) = correct [OK]

Hint: Use make([]int, size) to create int slice [OK]

Common Mistakes:

• Using make(int, 5) instead of make([]int, 5)
• Confusing array and slice syntax
• Initializing slice with single element instead of length

3. Consider the following Go code using Union Find:

parent := []int{0, 1, 2, 3, 4}

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

func union(a, b int) {
    rootA := find(a)
    rootB := find(b)
    if rootA != rootB {
        parent[rootB] = rootA
    }
}

union(0, 1)
union(1, 2)
union(3, 4)

fmt.Println(find(2), find(4))

What is the output?

medium

A. 1 3

B. 2 4

C. 0 4

D. 0 3

Solution

1. Step 1: Trace union operations

   union(0,1) merges sets of 0 and 1, so parent[1] = 0. union(1,2) merges sets of 1 and 2, so parent[2] = 0 (since find(1) = 0). union(3,4) merges sets of 3 and 4, so parent[4] = 3.

2. Step 2: Find roots of 2 and 4

   find(2) follows parent[2] = 0, so root is 0. find(4) follows parent[4] = 3, so root is 3.

3. Final Answer:

   0 3 -> Option D

4. Quick Check:

   Roots after unions = 0 and 3 [OK]

Hint: Follow parent links to find root [OK]

Common Mistakes:

• Not applying path compression in find
• Mixing up which root belongs to which element
• Assuming union merges by value instead of root

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

parent := []int{0, 1, 2, 3, 4}

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

func union(a, b int) {
    rootA := find(a)
    rootB := find(b)
    if rootA != rootB {
        parent[rootA] = rootB
    }
}

union(0, 1)
union(1, 2)
fmt.Println(find(2))

medium

A. Incorrect union direction causing unbalanced tree

B. Missing path compression in find function

C. Parent array not initialized properly

D. Using recursion in find causes stack overflow

Solution

1. Step 1: Analyze find function

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

2. Step 2: Understand impact of missing path compression

   Without path compression, the tree can become deep, causing slower future finds. The union logic is correct, and parent array is initialized properly.

3. Final Answer:

   Missing path compression in find function -> Option B

4. Quick Check:

   Path compression missing = bug [OK]

Hint: Add parent[x] = find(parent[x]) in find [OK]

Common Mistakes:

• Thinking union direction is always wrong
• Assuming recursion causes stack overflow here
• Ignoring path compression benefits

5. You have 6 elements (0 to 5) initially separate. After these unions: union(0,1), union(2,3), union(4,5), union(1,2), which of the following pairs are in the same set?

hard

A. 2 and 4

B. 1 and 5

C. 0 and 3

D. 3 and 5

Solution

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

   union(0,1) merges sets {0,1}, union(2,3) merges {2,3}, union(4,5) merges {4,5}, union(1,2) merges sets containing 1 and 2, so {0,1,2,3} become one set.

2. Step 2: Check pairs

   Pair 0 and 3 are in the same set {0,1,2,3}. Pairs 1 and 5, 2 and 4, 3 and 5 are in different sets.

3. Final Answer:

   0 and 3 -> Option C

4. Quick Check:

   Unions merge sets correctly = 0 and 3 same set [OK]

Hint: Merge sets stepwise, check membership [OK]

Common Mistakes:

• Assuming all unions merge all elements
• Mixing sets after union(1,2)
• Confusing pairs in different sets