Union Find Disjoint Set Data Structure in DSA C# - Execution Trace

Concept Flow - Union Find Disjoint Set Data Structure

Initialize each element as its own set

↓

Find root of element A

↓

Find root of element B

↓

Are roots different?

No→Sets already united

Yes↓

Union: Attach one root to another

↓

Update parent pointers

↓

Sets merged

Start with each element separate. To union, find roots of both elements. If roots differ, link one root to the other to merge sets.

Execution Sample

DSA C#

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

void Union(int a, int b) {
  int rootA = Find(a);
  int rootB = Find(b);
  if (rootA != rootB) parent[rootB] = rootA;
}

Find returns the root parent of an element with path compression. Union merges two sets by linking roots.

Execution Table

Step	Operation	Element(s) Involved	Parent Array State	Pointer Changes	Visual State
1	Initialize sets	Elements 0 to 4	[0,1,2,3,4]	Each element points to itself	┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐ │ data:0 │ │ data:1 │ │ data:2 │ │ data:3 │ │ data:4 │ │ next:0 │ │ next:1 │ │ next:2 │ │ next:3 │ │ next:4 │ └────────┘ └────────┘ └────────┘ └────────┘ └────────┘ head head head head head
2	Union	Union(0,1)	[0,0,2,3,4]	parent[1] = 0	Before: ┌────────┐ ┌────────┐ │ data:0 │ │ data:1 │ │ next:0 │ │ next:1 │ └────────┘ └────────┘ head head After: ┌────────┐ ┌────────┐ │ data:0 │ │ data:1 │ │ next:0 │ │ next:0 │ └────────┘ └────────┘ head points to 0
3	Union	Union(2,3)	[0,0,2,2,4]	parent[3] = 2	Before: ┌────────┐ ┌────────┐ │ data:2 │ │ data:3 │ │ next:2 │ │ next:3 │ └────────┘ └────────┘ head head After: ┌────────┐ ┌────────┐ │ data:2 │ │ data:3 │ │ next:2 │ │ next:2 │ └────────┘ └────────┘ head points to 2
4	Find	Find(1)	[0,0,2,2,4]	Path compression: parent[1] updated to 0	Traverse: 1 -> 0 (root) Parent array unchanged as parent[1] already 0
5	Union	Union(1,2)	[0,0,0,2,4]	parent[2] = 0	Before: ┌────────┐ ┌────────┐ ┌────────┐ │ data:0 │ │ data:1 │ │ data:2 │ │ next:0 │ │ next:0 │ │ next:2 │ └────────┘ └────────┘ └────────┘ head points0 head After: ┌────────┐ ┌────────┐ ┌────────┐ │ data:0 │ │ data:1 │ │ data:2 │ │ next:0 │ │ next:0 │ │ next:0 │ └────────┘ └────────┘ └────────┘ head points0 points0
6	Find	Find(3)	[0,0,0,0,4]	Path compression: parent[3] updated to 0	Traverse: 3 -> 2 -> 0 (root) Update parent[3] = 0 Parent array: [0,0,0,0,4]
7	Union	Union(3,4)	[0,0,0,0,0]	parent[4] = 0	Before: ┌────────┐ ┌────────┐ │ data:3 │ │ data:4 │ │ next:0 │ │ next:4 │ └────────┘ └────────┘ points0 head After: ┌────────┐ ┌────────┐ │ data:3 │ │ data:4 │ │ next:0 │ │ next:0 │ └────────┘ └────────┘ points0 points0
8	Find	Find(4)	[0,0,0,0,0]	No change, parent[4] = 0	Traverse: 4 -> 0 (root) Parent array unchanged
9	Check	Are 1 and 4 connected?	[0,0,0,0,0]	Find(1)=0, Find(4)=0	Both have same root 0, so connected
10	End	All unions done	[0,0,0,0,0]	No changes	All elements in one set with root 0

💡 All elements merged into one set with root 0, no further unions needed

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 5	After Step 6	After Step 7	Final
parent	[0,1,2,3,4]	[0,0,2,3,4]	[0,0,2,2,4]	[0,0,0,2,4]	[0,0,0,0,4]	[0,0,0,0,0]	[0,0,0,0,0]
rootA (Union)	N/A	0 (for 0)	2 (for 2)	0 (for 1)	N/A	0 (for 3)	N/A
rootB (Union)	N/A	1 (for 1)	3 (for 3)	2 (for 2)	N/A	4 (for 4)	N/A

Key Moments - 3 Insights

Why do we update parent pointers during Find (path compression)?

Updating parent pointers during Find flattens the tree, making future Finds faster. See Step 6 where parent[3] changes from 2 to 0, reducing traversal length.

What happens if we try to union two elements already in the same set?

If roots are the same, no union happens. Step 9 shows Find(1) and Find(4) both return 0, so no pointer changes occur.

Why does parent array start with each element pointing to itself?

Each element starts as its own set (root). Step 1 shows parent[i] = i, meaning no unions yet.

Visual Quiz - 3 Questions

Look at the execution table at Step 5, what is the parent of element 2 after the union?

A 1

B 2

C 0

D 3

💡 Hint

Check the 'Parent Array State' column at Step 5 in the execution table.

At which step does element 3's parent change to 0 due to path compression?

A Step 4

B Step 6

C Step 7

D Step 9

💡 Hint

Look for 'Path compression' and parent updates for element 3 in the execution table.

If we skip path compression in Find, how would the parent array after Step 6 differ?

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

B [0,0,0,0,4]

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

D [0,0,2,2,4]

💡 Hint

Compare parent array states with and without path compression at Step 6.

Concept Snapshot

Union Find DS:
- Each element starts as its own set (parent points to self)
- Find(x): returns root parent with path compression
- Union(a,b): link roots if different
- Path compression flattens tree for efficiency
- Used to track connected components quickly

Full Transcript

Union Find Disjoint Set Data Structure starts by initializing each element as its own set with parent pointing to itself. The Find operation locates the root parent of an element, applying path compression to speed up future queries by updating parent pointers directly to the root. The Union operation merges two sets by linking the root of one set to the root of another if they are different. This process is repeated to combine sets efficiently. The execution table shows step-by-step how parent pointers change and how the sets merge visually. Key moments clarify why path compression is important, what happens when union is called on elements already connected, and why initialization sets parents to themselves. The visual quiz tests understanding of parent array changes and path compression effects. The snapshot summarizes the core rules and behavior of Union Find.

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