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

Need a 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

Need a 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

Need a 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

Need a hint?

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