Union Find Disjoint Set Data Structure in DSA C#

Mental Model

Union Find keeps track of groups of items that are connected. It quickly tells if two items are in the same group or not.

Analogy: Imagine a classroom where students form friend groups. Union Find helps you quickly find if two students are in the same friend group or join two groups together.

0 [parent->0]
1 [parent->1]
2 [parent->2]
3 [parent->3]
4 [parent->4]

Each number is alone in its own group initially.

Dry Run Walkthrough

Input: Start with 5 elements (0 to 4), perform union(0,1), union(1,2), check if 0 and 2 are connected, then union(3,4), check if 0 and 4 are connected

Goal: Show how union merges groups and find checks if two elements share the same group

Step 1: union(0,1) merges groups of 0 and 1

0 [parent->0]
1 [parent->0]
2 [parent->2]
3 [parent->3]
4 [parent->4]

Why: We connect 1 to 0's group to form a bigger group

Step 2: union(1,2) merges groups of 1 and 2

0 [parent->0]
1 [parent->0]
2 [parent->0]
3 [parent->3]
4 [parent->4]

Why: We connect 2 to the group that contains 0 and 1

Step 3: find(0) and find(2) both return 0, so connected

0 [parent->0]
1 [parent->0]
2 [parent->0]
3 [parent->3]
4 [parent->4]

Why: Both 0 and 2 share the same root, so they are in the same group

Step 4: union(3,4) merges groups of 3 and 4

0 [parent->0]
1 [parent->0]
2 [parent->0]
3 [parent->3]
4 [parent->3]

Why: We connect 4 to 3's group to form another group

Step 5: find(0) and find(4) return different roots (0 and 3), so not connected

0 [parent->0]
1 [parent->0]
2 [parent->0]
3 [parent->3]
4 [parent->3]

Why: 0 and 4 belong to different groups

Result:

0 -> 0
1 -> 0
2 -> 0
3 -> 3
4 -> 3

0 and 2 connected: true
0 and 4 connected: false

Annotated Code

DSA C#

using System;

class UnionFind {
    private int[] parent;
    private int[] rank;

    public UnionFind(int size) {
        parent = new int[size];
        rank = new int[size];
        for (int i = 0; i < size; i++) {
            parent[i] = i; // each element is its own parent
            rank[i] = 0; // initial rank is zero
        }
    }

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

    public void Union(int x, int y) {
        int rootX = Find(x);
        int rootY = Find(y);
        if (rootX == rootY) return; // already in same group

        // union by rank to keep tree shallow
        if (rank[rootX] < rank[rootY]) {
            parent[rootX] = rootY;
        } else if (rank[rootX] > rank[rootY]) {
            parent[rootY] = rootX;
        } else {
            parent[rootY] = rootX;
            rank[rootX]++;
        }
    }

    public bool Connected(int x, int y) {
        return Find(x) == Find(y);
    }

    public void PrintParents() {
        for (int i = 0; i < parent.Length; i++) {
            Console.WriteLine($"{i} -> {Find(i)}");
        }
    }
}

class Program {
    static void Main() {
        UnionFind uf = new UnionFind(5);
        uf.Union(0, 1);
        uf.Union(1, 2);
        uf.PrintParents();
        Console.WriteLine("0 and 2 connected: " + uf.Connected(0, 2));
        uf.Union(3, 4);
        uf.PrintParents();
        Console.WriteLine("0 and 4 connected: " + uf.Connected(0, 4));
    }
}

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

path compression flattens tree for faster future finds

int rootX = Find(x); int rootY = Find(y); if (rootX == rootY) return;

find roots and skip union if already connected

if (rank[rootX] < rank[rootY]) { parent[rootX] = rootY; } else if (rank[rootX] > rank[rootY]) { parent[rootY] = rootX; } else { parent[rootY] = rootX; rank[rootX]++; }

union by rank attaches smaller tree under bigger to keep shallow

return Find(x) == Find(y);

check if two elements share the same root

Output

0 -> 0

1 -> 0

2 -> 0

3 -> 3

4 -> 4

0 and 2 connected: True

0 -> 0

1 -> 0

2 -> 0

3 -> 3

4 -> 3

0 and 4 connected: False

Complexity Analysis

Time: O(α(n)) per operation, where α is the inverse Ackermann function, which is very slow growing and almost constant for all practical n, because path compression and union by rank keep trees flat

Space: O(n) for storing parent and rank arrays for n elements

vs Alternative: Naive union-find without path compression or rank can degrade to O(n) per operation, making this optimized version much faster

Edge Cases

Union on elements already in the same group

Union does nothing and does not change structure

DSA C#

if (rootX == rootY) return;

Find on single element (root of its own group)

Returns the element itself as root

DSA C#

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

Union on elements with equal rank

One root becomes parent and its rank increases by one

DSA C#

else { parent[rootY] = rootX; rank[rootX]++; }

When to Use This Pattern

When a problem asks to group items and quickly check if two items are connected or belong to the same group, use Union Find to efficiently manage these groups.

Common Mistakes

Mistake: Not using path compression causing slow find operations
Fix: Add path compression by setting parent[x] = Find(parent[x]) during find

Mistake: Not using union by rank causing tall trees and slow operations
Fix: Use rank to attach smaller tree under bigger tree during union

Mistake: Forgetting to check if roots are same before union
Fix: Add check if rootX == rootY before union to avoid unnecessary work

Summary

It keeps track of connected groups and quickly checks if two elements are in the same group.

Use it when you need to manage dynamic connectivity between elements efficiently.

The key is to keep trees flat using path compression and union by rank for fast 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