Union Find Disjoint Set Data Structure in DSA C# - 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 quickly find which set an element belongs to, and to merge two sets efficiently.

beginner

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

The 'Find' operation returns the representative or parent of the set that an element belongs to. It helps to check if two elements are in the same set.

beginner

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

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

intermediate

Why is path compression important in the Union Find data structure?

Path compression flattens the structure of the tree during 'Find' operations, making future 'Find' operations faster by directly linking nodes to their set representative.

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 number of sets

B The size of the set

C The representative element of the set

D The union of two sets

The 'Find' operation returns the representative or parent element of the set that contains the given element.

What is the main goal of the 'Union' operation?

A To split a set into two

B To delete an element from a set

C To find the size of a set

D To merge two sets into one

The 'Union' operation merges two disjoint sets into a single set.

Which technique improves the speed of the 'Find' operation by flattening the tree?

A Path compression

B Union by rank

C Breadth-first search

D Depth-first search

Path compression flattens the tree during 'Find' operations, speeding up future queries.

What does 'union by rank' help to achieve?

A Keeps the tree balanced by attaching smaller trees under larger ones

B Deletes duplicate elements

C Finds the representative faster

D Splits sets into smaller parts

'Union by rank' attaches the smaller tree under the root of the larger tree to keep the tree shallow.

If two elements have the same representative, what does it mean?

A They belong to different sets

B They belong to the same set

C They are not connected

D They are the root elements

If two elements share the same representative, they belong to the same 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.

Consider how the tree structure changes during operations.

Practice

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

easy

A. To store key-value pairs for fast lookup

B. To sort elements in ascending order

C. To efficiently track and merge groups of connected elements

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 over time.

2. Step 2: Compare with other data structures

   Sorting elements or storing key-value pairs are not the main goals of Union Find. It focuses on connectivity and grouping.

3. Final Answer:

   To efficiently track and merge groups of connected elements -> Option C

4. Quick Check:

   Union Find = track and merge groups [OK]

Hint: Union Find tracks connected groups efficiently [OK]

Common Mistakes:

• Confusing Union Find with sorting algorithms
• Thinking it stores key-value pairs like a dictionary
• Assuming it manages priority queues

2. Which of the following is the correct syntax to initialize a Union Find structure with 5 elements in C#?

easy

A. UnionFind uf = UnionFind(5);

B. var uf = new UnionFind(5);

C. var uf = UnionFind.New(5);

D. UnionFind uf = new UnionFind[] {5};

Solution

1. Step 1: Recall C# object initialization syntax

   In C#, to create a new object, we use the new keyword followed by the constructor call with parameters.

2. Step 2: Check each option

   var uf = new UnionFind(5); uses correct syntax: var uf = new UnionFind(5);. UnionFind uf = UnionFind(5); misses new. var uf = UnionFind.New(5); uses a non-standard method. UnionFind uf = new UnionFind[] {5}; tries to create an array incorrectly.

3. Final Answer:

   var uf = new UnionFind(5); -> Option B

4. Quick Check:

   Use 'new' keyword for object creation [OK]

Hint: Use 'new' keyword to create objects in C# [OK]

Common Mistakes:

• Omitting the 'new' keyword
• Using array syntax instead of constructor
• Calling non-existent static methods

3. Consider the following C# code using a Union Find structure:

var uf = new UnionFind(5);
uf.Union(0, 1);
uf.Union(1, 2);
bool connected = uf.Connected(0, 2);
Console.WriteLine(connected);

What will be the output?

medium

A. False

B. Runtime exception

C. Compilation error

D. True

Solution

1. Step 1: Analyze the union operations

   First, elements 0 and 1 are united, then 1 and 2 are united. This means 0, 1, and 2 are all connected.

2. Step 2: Check the connectivity query

   The call uf.Connected(0, 2) checks if 0 and 2 are in the same set, which they are after the unions.

3. Final Answer:

   True -> Option D

4. Quick Check:

   Union chains connect 0 and 2 = True [OK]

Hint: Union chains connect elements; check connectivity [OK]

Common Mistakes:

• Assuming only direct unions connect elements
• Confusing union with assignment
• Ignoring transitive connectivity

4. The following code snippet is intended to unite two sets and check if they are connected:

var uf = new UnionFind(3);
uf.Union(0, 1);
uf.Union(1, 3);
Console.WriteLine(uf.Connected(0, 3));

What is the problem with this code?

medium

A. Index 3 is out of range for Union Find of size 3

B. Union method does not exist

C. Connected method returns wrong type

D. No problem, code runs correctly

Solution

1. Step 1: Check Union Find size and indices used

   The Union Find is initialized with size 3, so valid indices are 0, 1, and 2.

2. Step 2: Identify invalid index usage

   The code calls uf.Union(1, 3) and uf.Connected(0, 3), but index 3 is invalid and out of range.

3. Final Answer:

   Index 3 is out of range for Union Find of size 3 -> Option A

4. Quick Check:

   Indices must be within 0 to size-1 [OK]

Hint: Check indices are within 0 to size-1 [OK]

Common Mistakes:

• Using indices equal to size or larger
• Assuming Union Find auto-expands
• Ignoring runtime exceptions from invalid indices

5. You have 6 elements (0 to 5) and perform unions: Union(0,1), Union(2,3), Union(4,5), Union(1,2). How many distinct sets remain?

hard

A. 2

B. 4

C. 3

D. 1

Solution

1. Step 1: Track unions step-by-step

   Initially, sets are {0}, {1}, {2}, {3}, {4}, {5} (6 sets).
   Union(0,1) merges {0} and {1} -> {0,1}, {2}, {3}, {4}, {5} (5 sets).
   Union(2,3) merges {2} and {3} -> {0,1}, {2,3}, {4}, {5} (4 sets).
   Union(4,5) merges {4} and {5} -> {0,1}, {2,3}, {4,5} (3 sets).
   Union(1,2) merges sets containing 1 and 2 -> {0,1,2,3}, {4,5} (2 sets).

2. Step 2: Count remaining distinct sets

   After all unions, only two sets remain: {0,1,2,3} and {4,5}.

3. Final Answer:

   2 -> Option A

4. Quick Check:

   Count sets after unions = 2 [OK]

Hint: Merge sets stepwise; count remaining groups [OK]

Common Mistakes:

• Counting unions instead of sets
• Forgetting transitive merges
• Assuming each union reduces sets by one always