Union Find Disjoint Set Data Structure in DSA Python - 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 different?] --No--> [Do nothing]
               |
              Yes
               |
               v
  [Union sets by linking roots]
               |
               v
  [Update parent pointers]
               |
               v
            [Done]

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

Execution Sample

DSA Python

parent = [0,1,2,3]
rank = [0,0,0,0]

def find(x):
    if parent[x] != x:
        parent[x] = find(parent[x])
    return parent[x]

def union(x, y):
    rootX = find(x)
    rootY = find(y)
    if rootX != rootY:
        if rank[rootX] < rank[rootY]:
            parent[rootX] = rootY
        elif rank[rootX] > rank[rootY]:
            parent[rootY] = rootX
        else:
            parent[rootY] = rootX
            rank[rootX] += 1

union(0,1)
union(2,3)
union(1,3)

This code creates 4 sets, unions 0 and 1, unions 2 and 3, then unions the sets containing 1 and 3.

Execution Table

Step	Operation	Nodes in Sets	Parent Array	Rank Array	Visual State
0	Initialize sets	{0}, {1}, {2}, {3}	[0, 1, 2, 3]	[0, 0, 0, 0]	0 1 2 3 │ │ │ │ ∅ ∅ ∅ ∅
1	union(0,1): find roots 0 and 1	{0}, {1}, {2}, {3}	[0, 1, 2, 3]	[0, 0, 0, 0]	No change yet
2	union(0,1): roots differ, link 1 to 0	{0,1}, {2}, {3}	[0, 0, 2, 3]	[1, 0, 0, 0]	0 │ 1 2 3 │ │ ∅ ∅
3	union(2,3): find roots 2 and 3	{0,1}, {2}, {3}	[0, 0, 2, 3]	[1, 0, 0, 0]	No change yet
4	union(2,3): roots differ, link 3 to 2	{0,1}, {2,3}	[0, 0, 2, 2]	[1, 0, 1, 0]	0 │ 1 2 │ 3
5	union(1,3): find roots of 1 and 3 root(1)=0, root(3)=2	{0,1}, {2,3}	[0, 0, 2, 2]	[1, 0, 1, 0]	No change yet
6	union(1,3): roots differ, link 2 to 0 (rank 1 vs 1, choose 0 as root and increase rank)	{0,1,2,3}	[0, 0, 0, 2]	[2, 0, 1, 0]	0 │ 1 2 │ 3
7	Path compression during find updates parent of 3 to 0	{0,1,2,3}	[0, 0, 0, 0]	[2, 0, 1, 0]	0 │ 1 2 3
8	End	{0,1,2,3}	[0, 0, 0, 0]	[2, 0, 1, 0]	All connected under root 0

💡 All unions done, sets merged as one with root 0

Variable Tracker

Variable	Start	After Step 2	After Step 4	After Step 6	After Step 7	Final
parent	[0,1,2,3]	[0,0,2,3]	[0,0,2,2]	[0,0,0,2]	[0,0,0,0]	[0,0,0,0]
rank	[0,0,0,0]	[1,0,0,0]	[1,0,1,0]	[2,0,1,0]	[2,0,1,0]	[2,0,1,0]

Key Moments - 3 Insights

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

We link roots because only roots represent entire sets. Linking non-root nodes breaks the structure. See steps 2 and 4 where roots are found before linking.

What is the purpose of the rank array?

Rank helps keep the tree shallow by attaching smaller trees under bigger ones. This is shown in step 6 where ranks decide which root becomes parent.

How does path compression improve find operation?

Path compression updates parents of nodes visited during find to point directly to root, flattening the tree. Step 7 shows parent of 3 updated to root 0.

Visual Quiz - 3 Questions

Look at the execution table at step 4, what is the parent array?

A [0, 1, 2, 3]

B [0, 0, 2, 2]

C [0, 0, 0, 2]

D [0, 0, 0, 0]

💡 Hint

Check the 'Parent Array' column at step 4 in the execution table.

At which step does the union of all elements into one set complete?

A Step 4

B Step 7

C Step 6

D Step 8

💡 Hint

Look for when the parent array shows all elements connected under one root.

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

A [0, 0, 0, 2]

B [0, 1, 2, 3]

C [0, 0, 0, 0]

D [1, 0, 2, 2]

💡 Hint

Without path compression, parent of 3 remains pointing to 2 as in step 6.

Concept Snapshot

Union Find DS:
- Each element starts as its own set
- find(x): follow parent pointers to root
- union(x,y): link roots if different
- Use rank to keep tree shallow
- Path compression flattens tree during find
- Efficient for connectivity queries

Full Transcript

Union Find Disjoint Set Data Structure starts with each element in its own set. To combine sets, we find the root parent of each element. If roots differ, we link one root to the other, merging sets. Rank array helps keep trees shallow by attaching smaller trees under bigger ones. Path compression updates parents during find to point directly to root, speeding up future finds. The execution trace shows initializing sets, performing unions step-by-step, updating parent and rank arrays, and applying path compression. This structure efficiently answers if two elements are in the same set.

Practice

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

easy

A. To efficiently track and merge groups of connected elements

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 which elements belong to which groups or sets, especially when these groups merge.

2. Step 2: Compare with other data structures

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

3. Final Answer:

   To efficiently track and merge groups of connected elements -> Option A

4. Quick Check:

   Union Find = track and merge groups [OK]

Hint: Union Find = manage connected groups fast [OK]

Common Mistakes:

• Confusing Union Find with sorting algorithms
• Thinking it stores key-value pairs
• Mixing it up with queue or stack data structures

2. Which of the following is the correct way to initialize a Union Find parent array for 5 elements in Python?

easy

A. parent = [None] * 5

B. parent = [1, 1, 1, 1, 1]

C. parent = [5, 5, 5, 5, 5]

D. parent = [0, 1, 2, 3, 4]

Solution

1. Step 1: Understand initialization of Union Find

   Each element starts as its own parent, so the parent array should have each index equal to itself.

2. Step 2: Check each option

   parent = [0, 1, 2, 3, 4] correctly sets parent[i] = i for i in 0 to 4. Others do not represent this.

3. Final Answer:

   parent = [0, 1, 2, 3, 4] -> Option D

4. Quick Check:

   Parent array init = self indices [OK]

Hint: Parent array starts with self indices [OK]

Common Mistakes:

• Setting all parents to 1 or a fixed number
• Using None which breaks find operations
• Confusing size array with parent array

3. What is the output of the following code?

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    def union(self, a, b):
        rootA = self.find(a)
        rootB = self.find(b)
        if rootA != rootB:
            self.parent[rootB] = rootA

uf = UnionFind(4)
uf.union(0, 1)
uf.union(2, 3)
uf.union(1, 3)
print(uf.parent)

medium

A. [0, 0, 0, 2]

B. [0, 0, 0, 0]

C. [0, 0, 2, 2]

D. [0, 1, 2, 3]

Solution

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

   Init: [0,1,2,3]
   Union(0,1): find(0)=0, find(1)=1 -> parent[1]=0 -> [0,0,2,3]
   Union(2,3): find(2)=2, find(3)=3 -> parent[3]=2 -> [0,0,2,2]
   Union(1,3): find(1)=0, find(3)=2 (sets parent[3]=2) -> parent[2]=0 -> [0,0,0,2]

2. Step 2: Verify print output

   No additional find calls before print. parent[3] points to 2 (now root 0), but not fully compressed to 0. Output: [0, 0, 0, 2]

3. Final Answer:

   [0, 0, 0, 2] -> Option A

4. Quick Check:

   parent = [0,0,0,2] after partial compression [OK]

Hint: Trace find calls and compression timing during union [OK]

Common Mistakes:

• Forgetting last union sets parent[2]=0 -> [0,0,2,2]
• Over-applying path compression -> [0,0,0,0]
• Ignoring unions entirely

4. Identify the bug in this Union Find union method:

def union(self, a, b):
    rootA = self.find(a)
    rootB = self.find(b)
    if rootA != rootB:
        self.parent[rootA] = rootB

medium

A. The find method is not called correctly

B. It should assign parent of rootB to rootA, not the other way

C. The if condition should be rootA == rootB

D. The method is missing a return statement

Solution

1. Step 1: Understand union direction

   Union should attach one root to the other to merge sets. Usually, parent of rootB is set to rootA or vice versa consistently.

2. Step 2: Check given code

   Code sets parent[rootA] = rootB, which reverses the usual convention and can cause incorrect tree structure or confusion.

3. Final Answer:

   It should assign parent of rootB to rootA, not the other way -> Option B

4. Quick Check:

   Union sets parent[rootB] = rootA [OK]

Hint: Union sets parent of second root to first root [OK]

Common Mistakes:

• Swapping roots incorrectly in union
• Not calling find before union
• Confusing equality check in if condition

5. Given a graph with 6 nodes and edges [(0,1), (1,2), (3,4)], how many connected components does the Union Find structure report after union operations on these edges?

hard

A. 4

B. 2

C. 3

D. 5

Solution

1. Step 1: Initialize 6 separate nodes

   Initially, each node is its own component: 6 components total.

2. Step 2: Perform unions for edges

   Union(0,1) merges nodes 0 and 1 -> components reduce to 5.
   Union(1,2) merges node 2 with 0-1 group -> components reduce to 4.
   Union(3,4) merges nodes 3 and 4 -> components reduce to 3.

3. Step 3: Count remaining components

   Node 5 remains alone -> total components = 3.

4. Final Answer:

   3 -> Option C

5. Quick Check:

   6 nodes - 3 unions = 3 components [OK]

Hint: Components = nodes - unions done [OK]

Common Mistakes:

• Counting edges instead of components
• Forgetting isolated nodes count as components
• Miscounting after unions