Union Find Disjoint Set Data Structure in DSA Rust - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the main purpose of the Union Find Disjoint Set data structure?

It helps to keep track of elements divided into disjoint sets and supports quick union and find operations to check if elements belong to the same set.

beginner

Explain the 'find' operation in Union Find Disjoint Set.

The 'find' operation returns the representative or root of the set that an element belongs to, helping to identify which set the element is in.

beginner

What does the 'union' operation do in the Union Find Disjoint Set?

The 'union' operation merges two sets into one by connecting their roots, so elements from both sets become part of the same set.

intermediate

Why is path compression important in Union Find?

Path compression flattens the structure of the tree during 'find' operations, making future finds faster by directly linking nodes to their root.

intermediate

What is the role of 'union by rank' or 'union by size' in Union Find?

It helps keep the tree shallow by always attaching the smaller tree under the root of the larger tree, improving efficiency of operations.

What does the 'find' operation return in a Union Find Disjoint Set?

A The union of two sets

B The size of the set

C The number of sets

D The root or representative of the set

The 'find' operation returns the root or representative element of the set that contains the given element.

What is the main benefit of path compression in Union Find?

A It reduces the height of trees for faster future finds

B It increases the number of sets

C It merges two sets

D It deletes elements from sets

Path compression flattens the tree structure, making future 'find' operations faster by reducing tree height.

Which operation merges two sets in Union Find?

A Find

B Union

C Split

D Insert

The 'union' operation merges two disjoint sets into one.

What does 'union by rank' help with?

A Keeping trees shallow for efficiency

B Increasing the number of sets

C Finding the size of a set

D Deleting sets

'Union by rank' attaches smaller trees under larger ones to keep the tree shallow and operations efficient.

If two elements have the same root, what does that mean?

A They belong to different sets

B They are not in any set

C They belong to the same set

D They are the roots themselves

Elements with the same root belong to the same disjoint set.

Describe how the Union Find Disjoint Set data structure works and why it is useful.

Think about how it groups elements and checks if they are connected.

Explain the optimizations 'path compression' and 'union by rank' in Union Find and how they improve performance.

Focus on how these techniques keep the structure efficient.

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