Union Find Disjoint Set Data Structure in DSA C# - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

What is the output after union operations?

Consider a Union Find data structure initialized with 5 elements (0 to 4). After performing unions Union(0, 1), Union(1, 2), and Union(3, 4), what is the parent array?

DSA C#

int[] parent = {0, 1, 2, 3, 4};
int[] rank = {0, 0, 0, 0, 0};

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

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

Union(parent, rank, 0, 1);
Union(parent, rank, 1, 2);
Union(parent, rank, 3, 4);

Console.WriteLine(string.Join(",", parent));

A [2, 2, 2, 4, 4]

B [1, 1, 1, 4, 4]

C [0, 1, 2, 3, 4]

D [0, 0, 0, 3, 3]

💡 Hint

Remember that union by rank attaches the smaller tree under the root of the larger tree.

After unions, elements 0,1,2 share root 0, and elements 3,4 share root 3. So parent array shows roots: [0,0,0,3,3].

❓ Predict Output

intermediate

What is the result of Find operation?

Given the parent array [0, 0, 0, 3, 3] and rank array [2, 0, 0, 1, 0], what is the result of Find(2)?

DSA C#

int[] parent = {0, 0, 0, 3, 3};
int[] rank = {2, 0, 0, 1, 0};

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

int result = Find(parent, 2);
Console.WriteLine(result);

A 2

B 3

C 0

D 1

💡 Hint

Follow the parent links until the root is found.

Element 2's parent is 0, which is its own parent, so Find(2) returns 0.

🔧 Debug

advanced

Identify the error in this Union Find implementation

What error does the following code produce when calling Union(0, 1)?

DSA C#

int[] parent = {0, 1, 2};
int[] rank = {0, 0, 0};

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

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

Union(parent, rank, 0, 1);

A Logical error: union attaches root incorrectly

B StackOverflowException due to infinite recursion

C IndexOutOfRangeException

D No error, runs correctly

💡 Hint

Check which parent is assigned to which root in the union logic.

The union logic mistakenly assigns parent[rootX] = rootY when rank[rootX] < rank[rootY], which is reversed. It should assign parent[rootX] = rootY in that case.

❓ Predict Output

advanced

What is the number of disjoint sets after unions?

Starting with 6 elements (0 to 5), after performing unions Union(0, 1), Union(2, 3), Union(4, 5), and Union(1, 2), how many disjoint sets remain?

DSA C#

int[] parent = {0, 1, 2, 3, 4, 5};
int[] rank = {0, 0, 0, 0, 0, 0};

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

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

Union(parent, rank, 0, 1);
Union(parent, rank, 2, 3);
Union(parent, rank, 4, 5);
Union(parent, rank, 1, 2);

int count = 0;
for (int i = 0; i < parent.Length; i++) {
    if (Find(parent, i) == i) count++;
}

Console.WriteLine(count);

A 2

B 3

C 4

D 1

💡 Hint

Count how many elements are their own parent after all unions.

Unions connect sets {0,1,2,3} and {4,5}, so two disjoint sets remain.

🧠 Conceptual

expert

Why is path compression important in Union Find?

Which option best explains the main benefit of path compression in the Union Find data structure?

A It balances the trees by rank to keep them shallow during unions.

B It reduces the height of trees, making future Find operations faster by directly linking nodes to their root.

C It prevents cycles in the graph by checking if two nodes are already connected.

D It sorts the elements in each set to allow binary search.

💡 Hint

Think about how Find operation speed improves after path compression.

Path compression flattens the tree by making nodes point directly to the root, speeding up future Find 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