Union Find Disjoint Set Data Structure in DSA Rust - Execution Trace

Concept Flow - Union Find Disjoint Set Data Structure

Initialize each element as its own set

↓

Find operation: Find root of element

↓

Are roots different?

No→Already connected, stop

Yes↓

Union operation: Attach one root to another

↓

Update parent pointers

↓

Sets merged, continue or stop

Start with each element alone. To connect two elements, find their roots. If roots differ, link one root to the other to merge sets.

Execution Sample

DSA Rust

let mut uf = UnionFind::new(5);
uf.union(0, 1);
uf.union(1, 2);
let connected = uf.connected(0, 2);

Create 5 elements, union 0 and 1, then 1 and 2, then check if 0 and 2 are connected.

Execution Table

Step	Operation	Nodes In Sets	Pointer Changes	Visual State
1	Initialize sets	0,1,2,3,4 each alone	parent = [0,1,2,3,4]	┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐ │ data:0 │ │ data:1 │ │ data:2 │ │ data:3 │ │ data:4 │ │ parent:0│ │ parent:1│ │ parent:2│ │ parent:3│ │ parent:4│ └────────┘ └────────┘ └────────┘ └────────┘ └────────┘
2	Union(0,1)	Sets: {0,1}, 2, 3, 4	parent[1] = 0	┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐ │ data:0 │ │ data:1 │ │ data:2 │ │ data:3 │ │ data:4 │ │ parent:0│ ──→│ parent:0│ │ parent:2│ │ parent:3│ │ parent:4│ └────────┘ └────────┘ └────────┘ └────────┘ └────────┘ head linked to 0
3	Union(1,2)	Sets: {0,1,2}, 3, 4	parent[2] = 0	┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐ │ data:0 │ │ data:1 │ │ data:2 │ │ data:3 │ │ data:4 │ │ parent:0│ ──→│ parent:0│ ──→│ parent:0│ │ parent:3│ │ parent:4│ └────────┘ └────────┘ └────────┘ └────────┘ └────────┘ head linked to 0 linked to 0
4	Find(0)	Sets unchanged	Find root of 0 is 0	No pointer changes
5	Find(2)	Sets unchanged	Find root of 2 is 0 (via parent[2])	No pointer changes
6	Connected(0,2)?	Sets unchanged	Roots equal (0 == 0), connected = true	No pointer changes
7	Union(3,4)	Sets: {0,1,2}, {3,4}	parent[4] = 3	┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐ │ data:0 │ │ data:1 │ │ data:2 │ │ data:3 │ │ data:4 │ │ parent:0│ ──→│ parent:0│ ──→│ parent:0│ │ parent:3│ ──→│ parent:3│ └────────┘ └────────┘ └────────┘ └────────┘ └────────┘
8	Connected(0,4)?	Sets unchanged	Roots differ (0 != 3), connected = false	No pointer changes

💡 Operations complete; unions merged sets, finds returned roots, connected checks compared roots.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 7	Final
parent	[0,1,2,3,4]	[0,0,2,3,4]	[0,0,0,3,4]	[0,0,0,3,3]	[0,0,0,3,3]

Key Moments - 3 Insights

Why does union(1,2) change parent of 2 to 0, not 1?

Because find(1) returns root 0, so union links root of 2 to root 0. See step 3 in execution_table where parent[2] = 0.

Why does find(2) return 0 as root?

Because parent[2] points to 0, which is its own parent. Step 5 shows find(2) follows parent to 0.

What happens if we check connected(0,4) after unions?

They are in different sets with roots 0 and 3, so connected returns false as in step 8.

Visual Quiz - 3 Questions

Look at the execution_table at step 3, what is the parent array after union(1,2)?

A [0,0,2,3,4]

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

C [0,0,0,3,4]

D [1,1,1,3,4]

💡 Hint

Check the 'Pointer Changes' column in step 3 of execution_table.

At which step does the union of elements 3 and 4 happen?

A Step 7

B Step 2

C Step 3

D Step 8

💡 Hint

Look for 'Union(3,4)' operation in execution_table.

If we call connected(0,4) after step 7, what will be the result?

A true

B false

C error

D depends on union order

💡 Hint

See step 8 in execution_table where roots differ and connected is false.

Concept Snapshot

Union Find DS manages sets by linking roots.
Initialize: each element is its own parent.
Find: follow parent pointers to root.
Union: link one root to another.
Connected: check if roots are same.
Efficient for dynamic connectivity queries.

Full Transcript

Union Find Disjoint Set Data Structure starts with each element in its own set. The find operation locates the root parent of an element by following parent pointers. The union operation merges two sets by linking the root of one set to the root of another. Connected checks if two elements share the same root, meaning they are in the same set. The parent array tracks these links. This structure efficiently manages dynamic connectivity among elements.

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