Union Find Disjoint Set Data Structure in DSA Rust

Mental Model

Union Find keeps track of groups of items and quickly tells if two items are in the same group.

Analogy: Imagine groups of friends where each friend knows who their group leader is. When two groups meet, they pick one leader to represent both groups.

0 [leader]
1 -> 0
2 [leader]
3 -> 2
4 -> 2

Dry Run Walkthrough

Input: Start with 5 elements: 0,1,2,3,4 each in their own group. Perform union(1,0), union(3,4), union(4,2), then check if 1 and 2 are connected.

Goal: Combine groups step by step and check if two elements belong to the same group.

Step 1: union(1,0): connect group of 1 to group of 0

0 [leader]
1 -> 0
2 [leader]
3 [leader]
4 [leader]

Why: We merge 1's group into 0's group to keep track of connected elements.

Step 2: union(3,4): connect group of 3 to group of 4

0 [leader]
1 -> 0
2 [leader]
3 -> 4
4 [leader]

Why: We merge 3's group into 4's group to form a new combined group.

Step 3: union(4,2): connect group of 4 to group of 2

0 [leader]
1 -> 0
2 [leader]
3 -> 4
4 -> 2

Why: We merge 4's group into 2's group, combining 2,3,4 into one group.

Step 4: connected(1,2): check if 1 and 2 share the same leader

0 [leader]
1 -> 0
2 [leader]
3 -> 4
4 -> 2

Why: We find leaders of 1 and 2 to see if they belong to the same group.

Result:

0 [leader]
1 -> 0
2 [leader]
3 -> 4
4 -> 2
Answer: false (1 and 2 are not connected)

Annotated Code

DSA Rust

struct UnionFind {
    parent: Vec<usize>,
    rank: Vec<usize>,
}

impl UnionFind {
    fn new(size: usize) -> Self {
        Self {
            parent: (0..size).collect(),
            rank: vec![0; size],
        }
    }

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

    fn union(&mut self, x: usize, y: usize) {
        let root_x = self.find(x);
        let root_y = self.find(y);
        if root_x != root_y {
            if self.rank[root_x] < self.rank[root_y] {
                self.parent[root_x] = root_y; // attach smaller tree under bigger
            } else if self.rank[root_x] > self.rank[root_y] {
                self.parent[root_y] = root_x;
            } else {
                self.parent[root_y] = root_x;
                self.rank[root_x] += 1; // increase rank if same
            }
        }
    }

    fn connected(&mut self, x: usize, y: usize) -> bool {
        self.find(x) == self.find(y)
    }
}

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

if self.parent[x] != x { self.parent[x] = self.find(self.parent[x]); // path compression }

compress path to leader to speed up future finds

let root_x = self.find(x); let root_y = self.find(y);

find leaders of both elements to decide union

if root_x != root_y { ... }

only union if leaders differ to avoid cycles

if self.rank[root_x] < self.rank[root_y] { self.parent[root_x] = root_y; } else if self.rank[root_x] > self.rank[root_y] { self.parent[root_y] = root_x; } else { self.parent[root_y] = root_x; self.rank[root_x] += 1; }

attach smaller tree under bigger to keep tree shallow

self.find(x) == self.find(y)

check if two elements share the same leader

Output

Connected(1, 2): false

Complexity Analysis

Time: O(α(n)) per operation because path compression and union by rank keep trees almost flat, where α is inverse Ackermann function which is very slow growing and practically constant.

Space: O(n) for storing parent and rank arrays for n elements.

vs Alternative: Compared to naive union without path compression, this approach is much faster for many operations because it avoids long chains by flattening trees.

Edge Cases

empty set (size 0)

UnionFind initializes empty arrays and operations do nothing or panic if accessed

DSA Rust

Self { parent: (0..size).collect(), rank: vec![0; size], }

union of already connected elements

No changes happen because roots are same, avoiding cycles

DSA Rust

if root_x != root_y { ... }

single element set

Element is its own leader, find returns itself

DSA Rust

if self.parent[x] != x { ... }

When to Use This Pattern

When a problem asks to group items and quickly check if two items are in the same group, use Union Find to efficiently manage and query these groups.

Common Mistakes

Mistake: Not using path compression in find, causing slow queries.
Fix: Add path compression by setting parent[x] to find(parent[x]) during find.

Mistake: Not using union by rank or size, causing tall trees and slow operations.
Fix: Attach smaller tree under bigger tree and update rank accordingly.

Summary

It keeps track of which elements belong to which groups and lets you quickly merge groups or check if two elements are connected.

Use it when you need to manage dynamic connectivity between elements efficiently.

The key is to keep trees flat by path compression and union by rank to make operations almost constant time.

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