Path Compression in Union Find in DSA Rust - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to find the root parent of a node in Union Find.

DSA Rust

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

Drag options to blanks, or click blank then click option'

Afind(parent, parent[x])

Bx + 1

Cx

Dparent[x]

Attempts:

3 left

💡 Hint

Common Mistakes

Returning parent[x] directly without recursion.

Returning x immediately without checking parent.

The find function recursively finds the root parent of x by calling itself on parent[x] until it reaches the root where parent[x] == x.

2fill in blank

medium

Complete the code to apply path compression in the find function.

DSA Rust

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

Drag options to blanks, or click blank then click option'

Afind(parent, parent[x])

Bfind(parent, x)

Cx

Dparent[x]

Attempts:

3 left

💡 Hint

Common Mistakes

Assigning parent[x] to x instead of the root.

Not updating parent[x] at all.

Path compression updates parent[x] to the root parent by recursively calling find on parent[x]. This flattens the tree for faster future queries.

3fill in blank

hard

Fix the error in the union function to correctly merge two sets.

DSA Rust

fn union(parent: &mut Vec<usize>, x: usize, y: usize) {
    let root_x = find(parent, x);
    let root_y = find(parent, y);
    if root_x != root_y {
        parent[[1]] = root_y;
    }
}

Drag options to blanks, or click blank then click option'

Ax

Broot_x

Croot_y

Dy

Attempts:

3 left

💡 Hint

Common Mistakes

Using x or y directly instead of their roots.

Assigning parent[root_y] instead of parent[root_x].

To merge two sets, we set the parent of root_x to root_y. This connects the root of one set to the root of the other.

4fill in blank

hard

Fill both blanks to implement union by rank optimization.

DSA Rust

fn union(parent: &mut Vec<usize>, rank: &mut Vec<usize>, x: usize, y: usize) {
    let root_x = find(parent, x);
    let root_y = find(parent, y);
    if root_x != root_y {
        if rank[root_x] < rank[[1]] {
            parent[root_x] = [2];
        } else if rank[root_y] < rank[root_x] {
            parent[root_y] = root_x;
        } else {
            parent[root_y] = root_x;
            rank[root_x] += 1;
        }
    }
}

Drag options to blanks, or click blank then click option'

Aroot_y

Broot_x

Cx

Dy

Attempts:

3 left

💡 Hint

Common Mistakes

Using x or y instead of root variables.

Assigning parent incorrectly reversing the direction.

Union by rank attaches the smaller tree under the root of the larger tree. When rank[root_x] < rank[root_y], we set parent[root_x] = root_y.

5fill in blank

hard

Fill all three blanks to implement path compression and union by rank in find and union functions.

DSA Rust

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

fn union(parent: &mut Vec<usize>, rank: &mut Vec<usize>, x: usize, y: usize) {
    let root_x = find(parent, x);
    let root_y = find(parent, y);
    if root_x != root_y {
        if rank[root_x] < rank[root_y] {
            parent[root_x] = [2];
        } else if rank[root_y] < rank[root_x] {
            parent[root_y] = root_x;
        } else {
            parent[root_y] = root_x;
            rank[root_x] += [3];
        }
    }
}

Drag options to blanks, or click blank then click option'

Afind(parent, parent[x])

Broot_y

C1

Droot_x

Attempts:

3 left

💡 Hint

Common Mistakes

Not updating parent[x] in find.

Incorrectly assigning parents in union.

Forgetting to increment rank.

In find, path compression sets parent[x] to the root by recursively calling find. In union, union by rank attaches smaller rank tree under larger and increments rank by 1 when ranks are equal.

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