Union Find Disjoint Set Data Structure in DSA Java - Execution Trace

Concept Flow - Union Find Disjoint Set Data Structure

  [Initialize each element as its own set]
             |
             v
  [Find root of element A] ←─────┐
             |                  |
             v                  |
  [Find root of element B]      |
             |                  |
             v                  |
  [Are roots same?] --Yes--> [Already connected]
             |
            No
             |
             v
  [Union sets by linking roots]
             |
             v
  [Update parent pointer]
             |
             v
          [Done]

Start with each element alone. To union, find roots of both sets. If different, link one root to the other. Repeat finds and unions to manage connected groups.

Execution Sample

DSA Java

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;
}

This code finds the root parent of elements and unions two sets by linking roots.

Execution Table

Step	Operation	Nodes Involved	Pointer Changes	Visual State
1	Initialize sets	0,1,2,3,4	parent[i] = i for i in 0..4	0→0, 1→1, 2→2, 3→3, 4→4 (each node points to itself)
2	Union(0,1)	0,1	parent[1] = 0	0→0, 1→0, 2→2, 3→3, 4→4
3	Union(1,2)	1,2	find(1)=0, parent[2] = 0	0→0, 1→0, 2→0, 3→3, 4→4
4	Find(2)	2	path compression: parent[2] = find(0)=0	0→0, 1→0, 2→0, 3→3, 4→4
5	Union(3,4)	3,4	parent[4] = 3	0→0, 1→0, 2→0, 3→3, 4→3
6	Union(2,4)	2,4	find(2)=0, find(4)=3, parent[3] = 0	0→0, 1→0, 2→0, 3→0, 4→3
7	Find(4)	4	path compression: parent[4] = find(3)=0	0→0, 1→0, 2→0, 3→0, 4→0
8	Check connected(1,4)	1,4	find(1)=0, find(4)=0, same root	Connected
9	Check connected(0,3)	0,3	find(0)=0, find(3)=0, same root	Connected
10	Check connected(1,3)	1,3	find(1)=0, find(3)=0, same root	Connected
11	Check connected(0,4)	0,4	find(0)=0, find(4)=0, same root	Connected
12	Check connected(0,2)	0,2	find(0)=0, find(2)=0, same root	Connected
13	Check connected(3,1)	3,1	find(3)=0, find(1)=0, same root	Connected
14	Check connected(0,5)	0,5	5 out of range, no parent	Error or Not connected

💡 All unions and finds complete; sets merged correctly; last check invalid due to element 5 not existing.

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,0,3,4]	[0,0,0,3,3]	[0,0,0,0,3]	[0,0,0,0,0]	[0,0,0,0,0]

Key Moments - 3 Insights

Why does find(2) update parent[2] to 0 during path compression?

Because in step 4, find(2) calls find(0) which returns 0, so parent[2] is updated to point directly to root 0, speeding future finds (see execution_table step 4).

Why do we link root of one set to another in union instead of just any node?

Linking roots ensures the structure remains a tree without cycles. In step 6, we link root 3 to root 0, not just node 4, to keep sets connected properly (see execution_table step 6).

What happens if we try to find or union an element outside the initialized range?

As in step 14, element 5 does not exist, so no parent is found, causing an error or 'not connected' result (see execution_table step 14).

Visual Quiz - 3 Questions

Look at the execution_table at step 3, what is the parent of node 2 after union(1,2)?

A 2

B 1

C 0

D 3

💡 Hint

Check the 'Pointer Changes' and 'Visual State' columns at step 3.

At which step does path compression update parent[4] to 0?

A Step 6

B Step 7

C Step 5

D Step 8

💡 Hint

Look for 'path compression' mention in the 'Pointer Changes' column.

If we skip path compression in find, how would the parent array after step 7 change?

A [0,0,0,3,3]

B [0,0,0,0,3]

C [0,0,0,0,0]

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

💡 Hint

Compare 'Visual State' at step 7 with and without path compression.

Concept Snapshot

Union Find Disjoint Set:
- Each element starts as its own parent.
- find(x): returns root parent of x, compresses path.
- union(a,b): links root of b to root of a if different.
- Efficient for checking connected components.
- Path compression speeds up repeated finds.

Full Transcript

Union Find Disjoint Set starts with each element in its own group. The find operation locates the root parent of an element, compressing the path for speed. The union operation connects two groups by linking one root to another. This structure helps quickly check if two elements are connected. The execution trace shows initializing parents, performing unions, path compression during finds, and checking connectivity. Key moments include understanding path compression, why roots are linked, and handling invalid elements.

Practice

1. What is the primary purpose of the Union Find Disjoint Set data structure?

easy

A. To efficiently manage and query connected components in a set

B. To sort elements in ascending order

C. To store key-value pairs for fast lookup

D. To implement a queue with fast enqueue and dequeue

Solution

1. Step 1: Understand the purpose of Union Find

   The Union Find data structure is designed to keep track of elements partitioned into disjoint sets and quickly find which set an element belongs to.

2. Step 2: Compare with other options

   Sorting, key-value storage, and queue operations are unrelated to Union Find's main goal.

3. Final Answer:

   To efficiently manage and query connected components in a set -> Option A

4. Quick Check:

   Union Find = Manage connected components [OK]

Hint: Union Find tracks groups, not order or key-value pairs [OK]

Common Mistakes:

• Confusing Union Find with sorting algorithms
• Thinking it stores key-value pairs like a map
• Assuming it implements queue operations

2. Which of the following is the correct way to initialize a Union Find structure for 5 elements in Java?

easy

A. UnionFind uf = new UnionFind[5];

B. UnionFind uf = new UnionFind(); uf.init(5);

C. UnionFind uf = new UnionFind(5);

D. UnionFind uf = new UnionFind(0, 5);

Solution

1. Step 1: Recognize typical Union Find constructor

   Usually, Union Find is initialized by passing the number of elements to its constructor, like new UnionFind(5).

2. Step 2: Check other options for syntax errors

   UnionFind uf = new UnionFind(); uf.init(5); suggests a separate init method which is uncommon; UnionFind uf = new UnionFind[5]; tries to create an array of UnionFind objects, not a single instance; UnionFind uf = new UnionFind(0, 5); uses two parameters which is not standard.

3. Final Answer:

   UnionFind uf = new UnionFind(5); -> Option C

4. Quick Check:

   Constructor with size parameter = UnionFind uf = new UnionFind(5); [OK]

Hint: Union Find needs size in constructor, no separate init [OK]

Common Mistakes:

• Trying to create an array of UnionFind instead of one instance
• Using multiple parameters in constructor incorrectly
• Assuming an init method is required after construction

3. Consider the following Java code using Union Find:

UnionFind uf = new UnionFind(5);
uf.union(0, 1);
uf.union(1, 2);
boolean connected = uf.connected(0, 2);
System.out.println(connected);

What will be the output?

medium

A. Runtime exception

B. false

C. Compilation error

D. true

Solution

1. Step 1: Trace union operations

   First, 0 and 1 are joined, then 1 and 2 are joined. This means 0, 1, and 2 belong to the same set.

2. Step 2: Check connected query

   Querying if 0 and 2 are connected returns true because they share the same root after unions.

3. Final Answer:

   true -> Option D

4. Quick Check:

   Union chains connect 0 and 2 = true [OK]

Hint: Union chains connect elements; connected returns true [OK]

Common Mistakes:

• Assuming union does not link transitive elements
• Confusing union with overwrite of sets
• Expecting false because 0 and 2 were not directly united

4. The following code snippet has a bug. What is the error?

UnionFind uf = new UnionFind(3);
uf.union(0, 1);
uf.union(1, 2);
System.out.println(uf.connected(0, 3));

medium

A. Index out of bounds error at connected(0, 3)

B. No error, prints false

C. Compilation error due to wrong method call

D. Logical error, should print true

Solution

1. Step 1: Check the size and indices used

   The UnionFind is initialized with size 3, so valid indices are 0, 1, and 2. Index 3 is invalid.

2. Step 2: Identify the error at connected call

   Calling connected(0, 3) accesses an invalid index, causing an index out of bounds error.

3. Final Answer:

   Index out of bounds error at connected(0, 3) -> Option A

4. Quick Check:

   Invalid index access = Index out of bounds error [OK]

Hint: Check indices are within 0 to size-1 [OK]

Common Mistakes:

• Assuming connected returns false for invalid index
• Ignoring array bounds in Union Find
• Thinking compilation error occurs instead of runtime error

5. You have 6 elements (0 to 5). After performing unions: union(0,1), union(2,3), union(4,5), union(1,2), how many distinct sets remain?

hard

A. 3

B. 2

C. 1

D. 4

Solution

1. Step 1: Analyze unions step-by-step

   Initially, sets are {0}, {1}, {2}, {3}, {4}, {5}. - union(0,1) merges {0} and {1} -> {0,1} - union(2,3) merges {2} and {3} -> {2,3} - union(4,5) merges {4} and {5} -> {4,5} - union(1,2) merges sets containing 1 and 2 -> merges {0,1} and {2,3} -> {0,1,2,3}

2. Step 2: Count remaining distinct sets

   After all unions, sets are {0,1,2,3} and {4,5}, so total 2 sets remain.

3. Step 3: Re-examine options

   Options say 3, 2, 1, 4. The correct count is 2.

4. Final Answer:

   2 -> Option B

5. Quick Check:

   Union merges sets, final count = 2 [OK]

Hint: Count sets after unions by merging connected groups [OK]

Common Mistakes:

• Counting unions instead of distinct sets
• Forgetting transitive merges
• Assuming each union reduces sets by one without checking connections