Union Find Disjoint Set Data Structure in DSA C# - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize the parent array so each element is its own parent.

DSA C#

for (int i = 0; i < n; i++) {
    parent[i] = [1];
}

Drag options to blanks, or click blank then click option'

A0

Bi

Cn

D-1

Attempts:

3 left

💡 Hint

Common Mistakes

Setting all parents to 0 or -1 instead of their own index.

Each element starts as its own parent, so parent[i] = i.

2fill in blank

medium

Complete the code to find the root parent of element x with path compression.

DSA C#

public int Find(int x) {
    if (parent[x] != x) {
        parent[x] = [1];
    }
    return parent[x];
}

Drag options to blanks, or click blank then click option'

Ax + 1

Bx

Cparent[parent[x]]

DFind(parent[x])

Attempts:

3 left

💡 Hint

Common Mistakes

Assigning parent[x] to x or a wrong index instead of the root.

Path compression sets parent[x] to the root parent found by recursively calling Find.

3fill in blank

hard

Fix the error in the Union method to correctly union two sets by rank.

DSA C#

public void Union(int x, int y) {
    int rootX = Find(x);
    int rootY = Find(y);
    if (rootX != rootY) {
        if (rank[rootX] < rank[rootY]) {
            parent[rootX] = rootY;
        } else if (rank[rootX] > rank[rootY]) {
            parent[rootY] = [1];
        } else {
            parent[rootY] = rootX;
            rank[rootX]++;
        }
    }
}

Drag options to blanks, or click blank then click option'

ArootY

Bx

CrootX

Dy

Attempts:

3 left

💡 Hint

Common Mistakes

Swapping rootX and rootY in parent assignment.

When rank[rootX] > rank[rootY], rootY's parent should be rootX.

4fill in blank

hard

Fill both blanks to complete the method that checks if two elements are in the same set.

DSA C#

public bool Connected(int x, int y) {
    return Find(x) [1] Find(y);
}

Drag options to blanks, or click blank then click option'

A==

B!=

C<=

D>=

Attempts:

3 left

💡 Hint

Common Mistakes

Using inequality operator which returns wrong result.

Two elements are connected if their root parents are equal.

5fill in blank

hard

Fill all three blanks to complete the Union method with path compression and rank optimization.

DSA C#

public void Union(int x, int y) {
    int rootX = [1];
    int rootY = [2];
    if (rootX != rootY) {
        if (rank[rootX] < rank[rootY]) {
            parent[rootX] = [3];
        } else if (rank[rootX] > rank[rootY]) {
            parent[rootY] = rootX;
        } else {
            parent[rootY] = rootX;
            rank[rootX]++;
        }
    }
}

Drag options to blanks, or click blank then click option'

AFind(x)

BFind(y)

CrootY

DrootX

Attempts:

3 left

💡 Hint

Common Mistakes

Using variables x or y directly instead of their roots.

Use Find(x) and Find(y) to get roots, then assign parent[rootX] = rootY if rank[rootX] < rank[rootY].

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