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

Union Find Disjoint Set Data Structure

📖 Scenario: Imagine you are managing groups of friends in a social app. You want to quickly find out if two people are in the same friend group and also combine groups when new friendships form.

🎯 Goal: You will build a simple Union Find (Disjoint Set) data structure in Rust. It will help you track friend groups by connecting people and checking if they belong to the same group.

📋 What You'll Learn

Create a vector called parent where each person is initially their own parent

Create a variable called size to store the number of people

Write a function find that returns the root parent of a person

Write a function union that connects two people by linking their root parents

Print the parent vector after some unions to show the groups

💡 Why This Matters

🌍 Real World

Union Find is used in social networks to manage friend groups, in network connectivity, and in clustering problems.

💼 Career

Understanding Union Find helps in solving problems related to grouping, connectivity, and efficient merging in coding interviews and real-world applications.

1

Create the initial parent vector

Create a vector called parent with 5 elements where each element is its own index (0 to 4). This means each person is their own parent initially.

DSA Rust

// Create a vector called parent with values 0usize, 1usize, 2usize, 3usize, 4usize
// Your code here

Hint

Use vec![0usize, 1usize, 2usize, 3usize, 4usize] to create the vector.

2

Add the size variable

Add a variable called size and set it to 5, representing the number of people.

DSA Rust

fn main() {
    let mut parent = vec![0usize, 1usize, 2usize, 3usize, 4usize];
    // Add a variable called size and set it to 5
    // Your code here
}

Hint

Just write let size = 5; below the parent vector.

3

Write the find function

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

DSA Rust

fn main() {
    let mut parent = vec![0usize, 1usize, 2usize, 3usize, 4usize];
    let size = 5;
}

// Write a function called find with signature:
// fn find(parent: &mut Vec, x: usize) -> usize {
//     // Your code here
// }

Hint

Use recursion and update parent[x] to the result of find(parent, parent[x]).

4

Write union function and print parent after unions

Write a function called union that takes a mutable reference to parent and two integers a and b. It connects the groups of a and b by setting the parent of b's root to a's root. Then, in main, call union to connect 0 and 1, then 1 and 2. Finally, print the parent vector.

DSA Rust

fn main() {
    let mut parent = vec![0usize, 1usize, 2usize, 3usize, 4usize];
    let size = 5;
    // Call union to connect 0 and 1
    // Call union to connect 1 and 2
    // Print the parent vector
    // Your code here
}

fn find(parent: &mut Vec, x: usize) -> usize {
    if parent[x] != x {
        parent[x] = find(parent, parent[x]);
    }
    parent[x]
}

// Write union function below
// fn union(parent: &mut Vec, a: usize, b: usize) {
//     // Your code here
// }

Hint

Use union(&mut parent, 0, 1); and union(&mut parent, 1, 2); then print parent.

Practice

1. What is the primary purpose of the Union Find Disjoint Set data structure?

easy

A. To sort elements in ascending order

B. To efficiently track and merge groups of connected elements

C. To store key-value pairs for fast lookup

D. To implement a queue with priority

Solution

1. Step 1: Understand the role of Union Find

   The Union Find data structure is designed to keep track of which elements belong to which groups or sets, especially when these groups merge.

2. Step 2: Compare with other data structures

   Sorting, key-value storage, and priority queues serve different purposes unrelated to grouping connected components.

3. Final Answer:

   To efficiently track and merge groups of connected elements -> Option B

4. Quick Check:

   Union Find = Group tracking [OK]

Hint: Union Find = fast group merging and checking [OK]

Common Mistakes:

• Confusing Union Find with sorting algorithms
• Thinking it stores key-value pairs
• Mixing it up with priority queues

2. Which of the following is the correct Rust syntax to create a new Union Find structure for 5 elements using the union_find crate?

easy

A. let uf = UnionFind::create(5);

B. let uf = UnionFind::init(5);

C. let uf = new UnionFind(5);

D. let uf = UnionFind::new(5);

Solution

1. Step 1: Recall Rust struct instantiation

   In Rust, constructors are usually implemented as associated functions named new, called with ::new().

2. Step 2: Check common method names

   Methods like create, init, or using new as a keyword are not standard Rust patterns.

3. Final Answer:

   let uf = UnionFind::new(5); -> Option D

4. Quick Check:

   Rust constructors use ::new() [OK]

Hint: Rust constructors use ::new() method [OK]

Common Mistakes:

• Using 'new' as a keyword instead of method
• Using non-standard method names like create or init
• Incorrect syntax like missing 'let' or wrong function call

3. Consider this Rust code using a Union Find structure with 4 elements (0 to 3):

let mut uf = UnionFind::new(4);
uf.union(0, 1);
uf.union(2, 3);
let connected = uf.equiv(1, 3);
println!("{}", connected);

What is the printed output?

medium

A. false

B. true

C. 1

D. Compilation error

Solution

1. Step 1: Analyze union operations

   Elements 0 and 1 are connected, and elements 2 and 3 are connected, but these two groups are separate.

2. Step 2: Check equivalence of 1 and 3

   Since 1 is in the first group and 3 in the second, they are not connected, so uf.equiv(1, 3) returns false.

3. Final Answer:

   false -> Option A

4. Quick Check:

   Groups: {0,1} and {2,3}, 1 and 3 not connected [OK]

Hint: Check if elements share the same root to confirm connection [OK]

Common Mistakes:

• Assuming union connects all elements globally
• Confusing union with adding elements
• Expecting true without checking groups

4. The following Rust code snippet using Union Find has a bug. What is the error?

let mut uf = UnionFind::new(3);
uf.union(0, 1);
uf.union(1, 3);

medium

A. No error, code runs fine

B. Syntax error in union method call

C. Index out of bounds error due to invalid element 3

D. Logical error: union does not merge sets

Solution

1. Step 1: Check the size of Union Find

   The Union Find is created for 3 elements indexed 0, 1, and 2.

2. Step 2: Analyze union calls

   The call uf.union(1, 3) tries to access element 3, which is out of range and causes an index error.

3. Final Answer:

   Index out of bounds error due to invalid element 3 -> Option C

4. Quick Check:

   Union Find size 3 means max index 2 [OK]

Hint: Check element indices are within Union Find size [OK]

Common Mistakes:

• Ignoring index range and assuming union works
• Thinking union method syntax is wrong
• Assuming no error occurs with invalid indices

5. You have 6 elements (0 to 5) initially disconnected. After these operations:

uf.union(0, 1);
uf.union(1, 2);
uf.union(3, 4);
uf.union(4, 5);
uf.union(2, 5);

How many distinct groups remain?

hard

A. 1

B. 2

C. 3

D. 4

Solution

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

   Union(0,1) connects 0 and 1; Union(1,2) connects 2 to that group; Union(3,4) connects 3 and 4; Union(4,5) connects 5 to that group.

2. Step 2: Final union merges groups

   Union(2,5) connects the group {0,1,2} with {3,4,5}, merging all into one group.

3. Final Answer:

   1 -> Option A

4. Quick Check:

   All elements connected after last union [OK]

Hint: Last union merges all groups into one [OK]

Common Mistakes:

• Counting groups before last union
• Not merging transitive connections
• Assuming unions only connect pairs, not groups