Union Find Disjoint Set Data Structure in DSA Rust - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize the parent array where each element is its own parent.

DSA Rust

let mut parent = vec![0; n];
for i in 0..n {
    parent[i] = [1];
}

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

An

B0

C-1

Di

Attempts:

3 left

💡 Hint

Common Mistakes

Setting all parents to 0 or -1 instead of their own index.

Using n as the parent value for all elements.

Each element is initially its own parent, so we set parent[i] = i for all i.

2fill in blank

medium

Complete the code to find the root parent of element x with path compression.

DSA Rust

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

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

Afind

Bunion

Croot

Dget_parent

Attempts:

3 left

💡 Hint

Common Mistakes

Using union instead of find inside the function.

Calling a non-existent function like root or get_parent.

The find function calls itself recursively to find the root parent and compresses the path.

3fill in blank

hard

Fix the error in the union function to correctly merge two sets by their root parents.

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'

Aroot_x

Broot_y

Cy

Dx

Attempts:

3 left

💡 Hint

Common Mistakes

Using x or y directly instead of their roots.

Setting parent of root_y instead of root_x.

We set the parent of root_x to root_y to merge the two sets.

4fill in blank

hard

Fill both blanks to check if two elements are in the same set.

DSA Rust

fn connected(parent: &mut Vec<usize>, x: usize, y: usize) -> bool {
    find(parent, [1]) == find(parent, [2])
}

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

Ax

By

Croot_x

Droot_y

Attempts:

3 left

💡 Hint

Common Mistakes

Using root_x or root_y which are not defined in this scope.

Comparing x and y directly without finding their roots.

We check if the roots of x and y are the same to determine if they are connected.

5fill in blank

hard

Fill all three blanks to implement union by rank optimization.

DSA Rust

fn union_by_rank(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] [1] rank[root_y] {
            parent[[2]] = root_x;
        } else if rank[root_x] < rank[root_y] {
            parent[[3]] = root_y;
        } else {
            parent[root_y] = root_x;
            rank[root_x] += 1;
        }
    }
}

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

A>

Broot_y

Croot_x

D<

Attempts:

3 left

💡 Hint

Common Mistakes

Mixing up the comparison operators.

Assigning parents incorrectly causing cycles.

We compare ranks to attach the smaller tree under the bigger one and update parents accordingly.

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