Path Compression in Union Find in DSA Rust - Build from Scratch

Path Compression in Union Find

📖 Scenario: Imagine you are managing a social network where people form friend groups. You want to quickly find out if two people are in the same friend group and efficiently merge groups when new friendships form.

🎯 Goal: You will build a Union Find data structure with path compression to quickly find the leader (representative) of each friend group. This helps in fast queries and merges.

📋 What You'll Learn

Create a vector called parent representing each person's parent in the friend group tree

Create a variable called size to store the number of people

Write a function find that uses path compression to find the leader of a person

Print the parent vector after some union operations to show the compressed paths

💡 Why This Matters

🌍 Real World

Union Find with path compression is used in social networks, network connectivity, and clustering to quickly find connected components.

💼 Career

Understanding Union Find and path compression is important for software engineers working on graph algorithms, network design, and optimization problems.

1

Create the parent vector for 5 people

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

DSA Rust

# Create a vector called parent where parent[i] = i for i in 0..5
# Your code here

Hint

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

2

Create the size variable

Create a variable called size and set it to 5 to represent the number of people.

DSA Rust

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

Hint

Just write let size = 5; inside the main function.

3

Write the find function with path compression

Write a function called find that takes parent as a mutable reference and an integer x. It should return the leader of x. Use path compression by setting parent[x] to the leader found recursively.

DSA Rust

fn main() {
    let mut parent = vec![0, 1, 2, 3, 4];
    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

Perform unions and print the parent vector

In the main function, perform these unions by setting the parent of one leader to another: union(0, 1), union(1, 2), union(3, 4). Use the find function to get leaders. Then print the parent vector after calling find on each element to compress paths.

DSA Rust

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

    // Perform unions: union(0, 1), union(1, 2), union(3, 4)
    // Use find to get leaders
    // Print the parent vector after path compression
    // Your code here
}

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

Hint

After unions and path compression, the parent vector should show leaders: 0 for 0,1,2 and 3 for 3,4.

Practice

1. What is the main purpose of path compression in the Union Find data structure?

easy

A. To merge two sets without checking their roots

B. To speed up future find operations by flattening the tree

C. To delete elements from the Union Find structure

D. To create new sets for each element

Solution

1. Step 1: Understand the role of path compression

   Path compression is used during the find operation to make the tree flatter by pointing nodes directly to the root.

2. Step 2: Effect on future operations

   This flattening reduces the time needed for future find calls, making them faster.

3. Final Answer:

   To speed up future find operations by flattening the tree -> Option B

4. Quick Check:

   Path compression = faster find [OK]

Hint: Path compression flattens trees to speed up finds [OK]

Common Mistakes:

• Thinking path compression merges sets
• Confusing path compression with union operation
• Believing it deletes elements

2. Which of the following Rust function signatures correctly represents a find method with path compression in a Union Find struct?

easy

A. fn find(&mut self, x: usize) -> usize

B. fn find(self, x: usize) -> usize

C. fn find(&self, x: usize) -> usize

D. fn find(x: usize) -> usize

Solution

1. Step 1: Identify mutability requirement

   Path compression modifies the parent array, so self must be mutable reference &mut self.

2. Step 2: Check return type and parameters

   The method takes an element index and returns its root as usize.

3. Final Answer:

   fn find(&mut self, x: usize) -> usize -> Option A

4. Quick Check:

   Mutable self needed for path compression [OK]

Hint: Path compression changes state, so use &mut self [OK]

Common Mistakes:

• Using &self which is immutable
• Taking ownership of self
• Missing self parameter

3. Given the following Rust code snippet implementing path compression in Union Find, what will be the output after calling uf.find(3)?

struct UnionFind {
    parent: Vec<usize>,
}

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

fn main() {
    let mut uf = UnionFind { parent: vec![0, 0, 1, 2] };
    let root = uf.find(3);
    println!("{}", root);
}

medium

A. 2

B. 3

C. 1

D. 0

Solution

1. Step 1: Trace the parent array before find

   Initial parent: [0, 0, 1, 2]. Element 3 points to 2, 2 points to 1, 1 points to 0.

2. Step 2: Perform find(3) with path compression

   find(3) calls find(2), which calls find(1), which calls find(0). Since 0 is its own parent, root is 0. Path compression sets parent[3] = 0 and parent[2] = 0.

3. Final Answer:

   0 -> Option D

4. Quick Check:

   Root of 3 after compression = 0 [OK]

Hint: Follow parent chain until self-parent, update parents [OK]

Common Mistakes:

• Stopping at immediate parent without recursion
• Not updating parent during compression
• Confusing indices with values

4. Identify the bug in this Rust find method with path compression and select the correct fix:

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

medium

A. Change == to != in the if condition

B. Remove the recursive call inside if

C. Return self.parent[self.parent[x]] instead

D. Add a loop instead of recursion

Solution

1. Step 1: Analyze the if condition logic

   The condition self.parent[x] == x means x is root, so no recursion needed. The code wrongly recurses when x is root.

2. Step 2: Correct the condition

   It should recurse only if x is not root, so condition must be self.parent[x] != x.

3. Final Answer:

   Change == to != in the if condition -> Option A

4. Quick Check:

   Recurse only if not root [OK]

Hint: Recurse only when parent differs from node [OK]

Common Mistakes:

• Recursing when node is root
• Forgetting base case
• Misusing equality in condition

5. You have a Union Find with 5 elements initialized as parent = [0,1,2,3,4]. After performing unions union(0,1), union(1,2), and union(3,4), what will be the parent array after calling find(2) with path compression if unions always attach the second root to the first root?

hard

A. [0, 0, 1, 3, 4]

B. [0, 1, 2, 3, 4]

C. [0, 0, 0, 3, 3]

D. [0, 0, 0, 4, 4]

Solution

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

   union(0,1): parent[1] = 0 -> [0,0,2,3,4] union(1,2): find(1)=0, find(2)=2, parent[2] = 0 -> [0,0,0,3,4] union(3,4): parent[4] = 3 -> [0,0,0,3,3]

2. Step 2: Call find(2) with path compression

   find(2) sees parent[2]=0 which is root, no change. Parents remain [0,0,0,3,3].

3. Final Answer:

   [0, 0, 0, 3, 3] -> Option C

4. Quick Check:

   Unions attach second root to first, path compression confirms roots [OK]

Hint: Track unions and compress paths to root [OK]

Common Mistakes:

• Not updating parents during union
• Confusing which root attaches to which
• Ignoring path compression effect