Union Find Disjoint Set Data Structure in DSA Go

Mental Model

Union Find keeps track of which items belong together in groups without overlap. It quickly tells if two items are in the same group or not.

Analogy: Imagine a classroom where students form friend groups. Union Find helps you quickly find out if two students are in the same friend group or join two groups together.

0 [parent->0]
1 [parent->1]
2 [parent->2]
3 [parent->3]
4 [parent->4]

Dry Run Walkthrough

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

Goal: Group elements 0,1,2 together and verify that 0 and 2 belong to the same group.

Step 1: Initialize each element as its own parent

0 [parent->0]
1 [parent->1]
2 [parent->2]
3 [parent->3]
4 [parent->4]

Why: Each element starts in its own group

Step 2: Union elements 0 and 1 by making 1's parent point to 0

0 [parent->0]
1 [parent->0]
2 [parent->2]
3 [parent->3]
4 [parent->4]

Why: 0 and 1 are now in the same group

Step 3: Union elements 1 and 2 by making 2's parent point to 0 (root of 1)

0 [parent->0]
1 [parent->0]
2 [parent->0]
3 [parent->3]
4 [parent->4]

Why: 0,1,2 are now in the same group

Step 4: Check if 0 and 2 have the same root parent

0 [parent->0]
1 [parent->0]
2 [parent->0]
3 [parent->3]
4 [parent->4]

Why: If roots match, they are connected

Result:

0 -> 0
1 -> 0
2 -> 0
3 -> 3
4 -> 4
Connected(0,2) = true

Annotated Code

DSA Go

package main

import "fmt"

type UnionFind struct {
	parent []int
	rank   []int
}

func NewUnionFind(size int) *UnionFind {
	uf := &UnionFind{
		parent: make([]int, size),
		rank:   make([]int, size),
	}
	for i := 0; i < size; i++ {
		uf.parent[i] = i // each element is its own parent
		uf.rank[i] = 0   // initial rank is zero
	}
	return uf
}

func (uf *UnionFind) Find(x int) int {
	if uf.parent[x] != x {
		uf.parent[x] = uf.Find(uf.parent[x]) // path compression
	}
	return uf.parent[x]
}

func (uf *UnionFind) Union(x, y int) {
	rootX := uf.Find(x) // find root of x
	rootY := uf.Find(y) // find root of y
	if rootX != rootY {
		// union by rank to keep tree shallow
		if uf.rank[rootX] < uf.rank[rootY] {
			uf.parent[rootX] = rootY
		} else if uf.rank[rootX] > uf.rank[rootY] {
			uf.parent[rootY] = rootX
		} else {
			uf.parent[rootY] = rootX
			uf.rank[rootX]++
		}
	}
}

func (uf *UnionFind) Connected(x, y int) bool {
	return uf.Find(x) == uf.Find(y) // true if same root
}

func main() {
	uf := NewUnionFind(5)
	uf.Union(0, 1)
	uf.Union(1, 2)
	fmt.Println("Parents after unions:")
	for i := 0; i < 5; i++ {
		fmt.Printf("%d -> %d\n", i, uf.Find(i))
	}
	fmt.Printf("Connected(0,2) = %v\n", uf.Connected(0, 2))
}

uf.parent[i] = i // each element is its own parent

initialize each element as its own group leader

uf.parent[x] = uf.Find(uf.parent[x]) // path compression

flatten tree by pointing directly to root to speed future finds

rootX := uf.Find(x) // find root of x

find group leader of x

rootY := uf.Find(y) // find root of y

find group leader of y

if rootX != rootY { ... }

only union if different groups

uf.parent[rootX] = rootY or uf.parent[rootY] = rootX

attach smaller tree under bigger tree to keep shallow

uf.rank[rootX]++

increase rank when trees are equal height

return uf.Find(x) == uf.Find(y)

check if two elements share the same group leader

Output

Parents after unions:

0 -> 0

1 -> 0

2 -> 0

3 -> 3

4 -> 4

Connected(0,2) = true

Complexity Analysis

Time: O(α(n)) per operation, where α is the inverse Ackermann function, practically constant because path compression and union by rank keep trees flat

Space: O(n) for storing parent and rank arrays for n elements

vs Alternative: Compared to naive union-find without path compression, this approach is much faster for many operations because it avoids tall trees and repeated traversals

Edge Cases

Union or find on single element

Returns itself as parent, no change

DSA Go

uf.parent[i] = i // each element is its own parent

Union of already connected elements

No change to structure, avoids unnecessary work

DSA Go

if rootX != rootY { ... }

Find on element with deep tree

Path compression flattens tree for future fast finds

DSA Go

uf.parent[x] = uf.Find(uf.parent[x]) // path compression

When to Use This Pattern

When a problem asks to group items and quickly check if two items are in the same group, use Union Find because it efficiently manages dynamic connectivity.

Common Mistakes

Mistake: Not using path compression causing slow find operations
Fix: Add path compression in Find to flatten the tree

Mistake: Not using union by rank causing tall trees and slow operations
Fix: Use union by rank to attach smaller tree under bigger tree

Mistake: Union operation without checking if roots differ, causing cycles
Fix: Check if roots differ before union to avoid redundant unions

Summary

It groups elements into sets and quickly checks if two elements belong to the same set.

Use it when you need to manage dynamic groups and connectivity queries efficiently.

The key is to keep trees flat using path compression and union by rank for fast operations.

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