Union Find Disjoint Set Data Structure in DSA Go - Build from Scratch

Union Find Disjoint Set Data Structure

📖 Scenario: Imagine you are managing a social network where people can form friend groups. You want to keep track of which people are in the same friend group efficiently.

🎯 Goal: Build a Union Find Disjoint Set data structure to group people and check if two people are in the same group.

📋 What You'll Learn

Create a slice called parent to represent each person's parent in the group

Create a slice called rank to keep track of the tree height for optimization

Write a function find to find the root parent of a person with path compression

Write a function union to join two groups by their root parents using rank

Check if two people are in the same group using find

💡 Why This Matters

🌍 Real World

Union Find is used in social networks to find friend groups, in network connectivity to check if computers are connected, and in clustering algorithms.

💼 Career

Understanding Union Find helps in solving problems related to grouping, connectivity, and efficient merging of sets, which are common in software engineering and competitive programming.

1

Create the initial parent and rank slices

Create two slices called parent and rank of size 5. Initialize parent so that each element is its own parent (0 to 4). Initialize rank with all zeros.

DSA Go

# Create slices parent and rank with size 5
# Initialize parent[i] = i and rank[i] = 0

Hint

Use a for loop from 0 to 4 to set each parent[i] to i and rank[i] to 0.

2

Write the find function with path compression

Write a function called find that takes parent slice and an integer x. It returns the root parent of x. Use recursion and path compression by setting parent[x] to the root parent.

DSA Go

package main

import "fmt"

func find(parent []int, x int) int {
    // Your code here
}

func main() {
    parent := make([]int, 5)
    rank := make([]int, 5)
    for i := 0; i < 5; i++ {
        parent[i] = i
        rank[i] = 0
    }
}

Hint

Check if parent[x] is not x. If so, set parent[x] to find(parent, parent[x]) and return it.

3

Write the union function using rank

Write a function called union that takes parent, rank slices and two integers x, y. Find root parents of x and y. If they are different, attach the smaller rank tree under the larger rank tree. If ranks are equal, attach y under x and increase rank[xRoot] by 1.

DSA Go

package main

import "fmt"

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

func union(parent []int, rank []int, x int, y int) {
    // Your code here
}

func main() {
    parent := make([]int, 5)
    rank := make([]int, 5)
    for i := 0; i < 5; i++ {
        parent[i] = i
        rank[i] = 0
    }
}

Hint

Use find to get roots. Compare ranks to decide which root becomes parent. Increase rank if equal.

4

Use union and find to group and check connections

In main, call union(parent, rank, 0, 1) and union(parent, rank, 1, 2). Then print find(parent, 0) and find(parent, 2) separated by a space. This shows the root parent of 0 and 2 after unions.

DSA Go

package main

import "fmt"

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

func union(parent []int, rank []int, x int, y int) {
    xRoot := find(parent, x)
    yRoot := find(parent, y)
    if xRoot == yRoot {
        return
    }
    if rank[xRoot]  rank[yRoot] {
        parent[yRoot] = xRoot
    } else {
        parent[yRoot] = xRoot
        rank[xRoot]++
    }
}

func main() {
    parent := make([]int, 5)
    rank := make([]int, 5)
    for i := 0; i < 5; i++ {
        parent[i] = i
        rank[i] = 0
    }
    // Your code here
}

Hint

Call union twice to join 0-1 and 1-2. Then print the root parents of 0 and 2 using find.

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