Union Find Disjoint Set Data Structure in DSA C# - Build from Scratch

Union Find Disjoint Set Data Structure

📖 Scenario: Imagine you have a group of friends, and you want to know which friends belong to the same friend circle. You can connect friends together and check if two friends are in the same circle.

🎯 Goal: Build a simple Union Find (Disjoint Set) data structure to connect friends and check if they belong to the same friend circle.

📋 What You'll Learn

Create an array called parent to represent each friend's parent in the set

Create an integer variable called size to store the number of friends

Write a method Find that returns the root parent of a friend

Write a method Union that connects two friends' sets

Write a method Connected that checks if two friends are in the same set

💡 Why This Matters

🌍 Real World

Union Find is used in social networks to find friend groups, in network connectivity to check if computers are connected, and in image processing to find connected regions.

💼 Career

Understanding Union Find helps in solving problems related to grouping, connectivity, and clustering which are common in software engineering interviews and real-world applications.

1

Create the parent array and size variable

Create an integer variable called size and set it to 5. Then create an integer array called parent with size size. Initialize each element of parent so that parent[i] = i for all i from 0 to size - 1.

DSA C#

// Your code here

Hint

Think of parent as each friend pointing to themselves at the start.

2

Write the Find method

Add a public method called Find that takes an integer x and returns the root parent of x. Use a while loop to find the root where parent[x] == x. Update x to parent[x] inside the loop.

DSA C#

    // Your code here
}

Hint

Keep moving up the parent chain until you find the root.

3

Write the Union method

Add a public method called Union that takes two integers x and y. Find the root parents of x and y using the Find method. If the roots are different, set the parent of rootY to rootX to connect the sets.

DSA C#

    // Your code here
}

Hint

Connect the root of one set to the root of the other to merge them.

4

Write the Connected method and test output

Add a public method called Connected that takes two integers x and y. Return true if Find(x) equals Find(y), otherwise false. Then create a Main method to create a UnionFind object, call Union(0, 1) and Union(1, 2), and print the result of Connected(0, 2) and Connected(0, 3).

DSA C#

    // Your code here
}

// Your code here

Hint

Use Console.WriteLine to print the results of Connected calls.

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