Disjoint set (Union-Find) in Data Structures Theory - Mini Project: Build & Apply

Disjoint Set (Union-Find) Basics

📖 Scenario: Imagine you are managing groups of friends at a party. You want to keep track of which friends belong to the same group. When two friends meet, their groups merge. You want to quickly find out if two friends are in the same group.

🎯 Goal: Build a simple disjoint set (union-find) structure to manage friend groups. You will create the initial groups, set up a helper structure, perform unions to merge groups, and complete the structure to find group leaders.

📋 What You'll Learn

Create a dictionary called parent where each friend is their own parent initially

Create a dictionary called rank to keep track of tree depth for each friend

Write a function find that returns the leader (root parent) of a friend

Write a function union that merges two friend groups by their leaders

💡 Why This Matters

🌍 Real World

Disjoint sets are used in social networks to find connected friend groups, in computer networks to detect connected components, and in image processing to group pixels.

💼 Career

Understanding disjoint sets is important for software engineers working on graph algorithms, network connectivity, clustering, and optimization problems.

1

Create initial parent dictionary

Create a dictionary called parent with keys 'Alice', 'Bob', 'Charlie', 'Diana', and 'Eve'. Set each friend's parent to themselves as a string value.

Data Structures Theory

# Create the parent dictionary where each friend is their own parent
# Your code here

Hint

Each friend starts as their own group leader, so their parent is themselves.

2

Create rank dictionary

Create a dictionary called rank with the same keys as parent. Set each friend's rank to 0 as an integer.

Data Structures Theory

parent = {
    'Alice': 'Alice',
    'Bob': 'Bob',
    'Charlie': 'Charlie',
    'Diana': 'Diana',
    'Eve': 'Eve'
}
# Create the rank dictionary with all ranks set to 0
# Your code here

Hint

Rank helps keep the tree shallow by tracking the depth of each group leader's tree.

3

Write the find function

Write a function called find that takes a friend's name as input and returns the root parent of that friend by following the parent links until the friend is their own parent.

Data Structures Theory

parent = {
    'Alice': 'Alice',
    'Bob': 'Bob',
    'Charlie': 'Charlie',
    'Diana': 'Diana',
    'Eve': 'Eve'
}
rank = {
    'Alice': 0,
    'Bob': 0,
    'Charlie': 0,
    'Diana': 0,
    'Eve': 0
}
# Define the find function to get the root parent of a friend
# Your code here

Hint

Keep following the parent until you find a friend who is their own parent.

4

Write the union function

Write a function called union that takes two friends, finds their root parents using find, and merges their groups by attaching the smaller rank tree under the larger rank tree. If ranks are equal, attach the second to the first and increase the first's rank by 1.

Data Structures Theory

parent = {
    'Alice': 'Alice',
    'Bob': 'Bob',
    'Charlie': 'Charlie',
    'Diana': 'Diana',
    'Eve': 'Eve'
}
rank = {
    'Alice': 0,
    'Bob': 0,
    'Charlie': 0,
    'Diana': 0,
    'Eve': 0
}
def find(friend):
    while parent[friend] != friend:
        friend = parent[friend]
    return friend

# Define the union function to merge two friend groups
# Your code here

Hint

Compare ranks to decide which root becomes the parent. Increase rank if both are equal.

Practice

1. What is the main purpose of a Disjoint Set (Union-Find) data structure?

easy

A. To sort elements in ascending order

B. To store key-value pairs for fast lookup

C. To efficiently keep track of which elements belong to which groups

D. To perform arithmetic calculations on sets

Solution

1. Step 1: Understand the role of Disjoint Set

   Disjoint Set is designed to manage groups of elements and quickly find which group an element belongs to.

2. Step 2: Compare with other options

   Sorting, key-value storage, and arithmetic are unrelated to Disjoint Set's main function.

3. Final Answer:

   To efficiently keep track of which elements belong to which groups -> Option C

4. Quick Check:

   Disjoint Set = group tracking [OK]

Hint: Disjoint Set = fast group membership check [OK]

Common Mistakes:

• Confusing Disjoint Set with sorting algorithms
• Thinking it stores key-value pairs like a dictionary
• Assuming it performs arithmetic on sets

2. Which of the following is the correct way to perform a union operation between two sets containing elements a and b in a Disjoint Set?

easy

A. merge(a, b)

B. union(a, b)

C. unionSet(a, b)

D. combine(a, b)

Solution

1. Step 1: Identify standard Disjoint Set operation names

   The common and standard name for merging two sets is union.

2. Step 2: Check other options

   Other names like unionSet, merge, or combine are not standard and may cause confusion.

3. Final Answer:

   union(a, b) -> Option B

4. Quick Check:

   Union operation = union(a, b) [OK]

Hint: Union operation is always called 'union' [OK]

Common Mistakes:

• Using non-standard method names
• Confusing union with find
• Assuming merge or combine are standard

3. Consider the following sequence of operations on a Disjoint Set with elements {1, 2, 3, 4}:

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

What is the result of find(4)?

medium

A. 4

B. 2

C. 3

D. 1

Solution

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

   union(1, 2) merges sets {1} and {2} -> {1, 2}. union(3, 4) merges {3} and {4} -> {3, 4}. union(2, 3) merges sets containing 2 and 3 -> {1, 2, 3, 4}.

2. Step 2: Find the representative of element 4

   After unions, all elements are in one set. The representative is usually the root of the first union, which is 1.

3. Final Answer:

   1 -> Option D

4. Quick Check:

   find(4) = 1 after unions [OK]

Hint: After unions, find returns the root representative [OK]

Common Mistakes:

• Assuming find(4) returns 4 itself
• Not merging sets correctly in union(2, 3)
• Confusing element with its set representative

4. Given the following incorrect Disjoint Set code snippet, what is the main error?

def union(a, b):
    rootA = find(a)
    rootB = find(b)
    if rootA != rootB:
        rootA = rootB  # Incorrect assignment

medium

A. The assignment does not update the parent of rootA

B. The find function is called incorrectly

C. The union function should return a value

D. The if condition should check rootA == rootB

Solution

1. Step 1: Analyze the union operation

   The union operation should update the parent of one root to the other to merge sets.

2. Step 2: Identify the error in assignment

   Assigning rootA = rootB only changes the local variable, not the parent array that tracks sets.

3. Final Answer:

   The assignment does not update the parent of rootA -> Option A

4. Quick Check:

   Union must update parent array, not local variables [OK]

Hint: Update parent array, not local variables [OK]

Common Mistakes:

• Assigning roots instead of updating parent array
• Confusing equality check in if condition
• Expecting union to return a value

5. You have 5 elements {1, 2, 3, 4, 5} initially in separate sets. After performing union(1, 2), union(3, 4), and union(2, 3), which of the following statements is true?

hard

A. Elements 1 and 4 belong to the same set

B. Element 5 belongs to the same set as element 1

C. Elements 2 and 5 belong to the same set

D. All elements belong to the same set

Solution

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

   union(1, 2) merges {1, 2}. union(3, 4) merges {3, 4}. union(2, 3) merges sets containing 2 and 3 -> {1, 2, 3, 4}.

2. Step 2: Check element 5's set

   Element 5 was never unioned, so it remains separate.

3. Final Answer:

   Elements 1 and 4 belong to the same set -> Option A

4. Quick Check:

   1 and 4 connected; 5 separate [OK]

Hint: Only unioned elements share sets; isolated remain separate [OK]

Common Mistakes:

• Assuming all elements merge after some unions
• Thinking element 5 is connected without union
• Confusing which elements are merged