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

Concept Flow - Union Find Disjoint Set Data Structure

Initialize each element as its own set

↓

Find operation: Find root of element

↓

Union operation: Merge two sets

↓

Update parent pointers

↓

Repeat for queries

↓

Sets merged

Start with each element alone. Find finds the root parent. Union merges sets by linking roots. Repeat to combine sets.

Execution Sample

DSA Typescript

class UnionFind {
  parent: number[];
  constructor(n: number) {
    this.parent = Array.from({ length: n }, (_, i) => i);
  }
  find(x: number): number {
    if (this.parent[x] !== x) this.parent[x] = this.find(this.parent[x]);
    return this.parent[x];
  }
  union(a: number, b: number): void {
    const rootA = this.find(a);
    const rootB = this.find(b);
    if (rootA !== rootB) this.parent[rootB] = rootA;
  }
}

This code creates sets for elements 0 to n-1, finds roots with path compression, and unions sets by linking roots.

Execution Table

Step	Operation	Elements Involved	Parent Array State	Pointer Changes	Visual State
1	Initialize sets	0,1,2,3,4	[0,1,2,3,4]	Each element points to itself	┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐ │ data:0 │ │ data:1 │ │ data:2 │ │ data:3 │ │ data:4 │ │ parent │ │ parent │ │ parent │ │ parent │ │ parent │ │ = 0 │ │ = 1 │ │ = 2 │ │ = 3 │ │ = 4 │ └────────┘ └────────┘ └────────┘ └────────┘ └────────┘
2	Union(0,1)	0,1	[0,0,2,3,4]	parent[1] = 0	┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐ │ data:0 │ │ data:1 │ │ data:2 │ │ data:3 │ │ data:4 │ │ parent │ │ parent │ │ parent │ │ parent │ │ parent │ │ = 0 │ │ = 0 │ │ = 2 │ │ = 3 │ │ = 4 │ └────────┘ └────────┘ └────────┘ └────────┘ └────────┘
3	Union(3,4)	3,4	[0,0,2,3,3]	parent[4] = 3	┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐ │ data:0 │ │ data:1 │ │ data:2 │ │ data:3 │ │ data:4 │ │ parent │ │ parent │ │ parent │ │ parent │ │ parent │ │ = 0 │ │ = 0 │ │ = 2 │ │ = 3 │ │ = 3 │ └────────┘ └────────┘ └────────┘ └────────┘ └────────┘
4	Union(1,3)	1,3	[0,0,2,0,3]	parent[3] = 0 (after find(1)=0, find(3)=3)	┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐ │ data:0 │ │ data:1 │ │ data:2 │ │ data:3 │ │ data:4 │ │ parent │ │ parent │ │ parent │ │ parent │ │ parent │ │ = 0 │ │ = 0 │ │ = 2 │ │ = 0 │ │ = 3 │ └────────┘ └────────┘ └────────┘ └────────┘ └────────┘
5	Find(4)	4	[0,0,2,0,0]	Path compression: parent[4] = find(3) = 0	┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐ │ data:0 │ │ data:1 │ │ data:2 │ │ data:3 │ │ data:4 │ │ parent │ │ parent │ │ parent │ │ parent │ │ parent │ │ = 0 │ │ = 0 │ │ = 2 │ │ = 0 │ │ = 0 │ └────────┘ └────────┘ └────────┘ └────────┘ └────────┘
6	Check if 2 and 4 connected	2,4	[0,0,2,0,0]	find(2)=2, find(4)=0, different roots	Sets are separate: {0,1,3,4} and {2}
7	Union(4,2)	2,4	[0,0,0,0,0]	parent[2] = 0	All elements connected: ┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐ │ data:0 │ │ data:1 │ │ data:2 │ │ data:3 │ │ data:4 │ │ parent │ │ parent │ │ parent │ │ parent │ │ parent │ │ = 0 │ │ = 0 │ │ = 0 │ │ = 0 │ │ = 0 │ └────────┘ └────────┘ └────────┘ └────────┘ └────────┘
8	Find(2)	2	[0,0,0,0,0]	find(2) = 0 (root)	No pointer changes (already compressed)
9	End	-	[0,0,0,0,0]	-	All elements in one set with root 0

💡 All unions processed; final parent array shows all elements connected under root 0

Variable Tracker

Variable	Start	After 2	After 3	After 4	After 5	After 7	Final
parent	[0,1,2,3,4]	[0,0,2,3,4]	[0,0,2,3,3]	[0,0,2,0,3]	[0,0,2,0,0]	[0,0,0,0,0]	[0,0,0,0,0]

Key Moments - 3 Insights

Why does the parent array change during find(4) in step 5?

In step 5, find(4) triggers path compression. The parent of 4 changes from 3 to 0 to speed up future finds. See execution_table row 5 for pointer change.

Why do we only update parent of rootB in union, not both?

Union links rootB's parent to rootA to merge sets without cycles. Updating both would break tree structure. See step 4 and 7 in execution_table.

Why is find used before union?

Find gets the root parent to know which sets elements belong to. Union merges only if roots differ, avoiding redundant merges. See steps 2,3,4 in execution_table.

Visual Quiz - 3 Questions

Look at the execution_table at step 5, what is the parent of element 4 after find(4)?

A 3

B 0

C 4

D 1

💡 Hint

Check the 'Pointer Changes' and 'Parent Array State' columns in step 5.

At which step does the parent of element 3 change to 0?

A Step 4

B Step 6

C Step 2

D Step 7

💡 Hint

Look at the 'Pointer Changes' column and 'Parent Array State' in step 4.

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

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

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

C [0,0,2,0,3]

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

💡 Hint

Compare step 4 and 5 parent arrays; path compression updates parent[4].

Concept Snapshot

Union Find Disjoint Set:
- Initialize each element as its own parent
- find(x): returns root parent with path compression
- union(a,b): link roots if different
- Efficiently tracks connected components
- Parent array shows set leaders
- Path compression flattens tree for speed

Full Transcript

Union Find Disjoint Set starts with each element in its own set. The find operation locates the root parent of an element, compressing paths to speed future queries. The union operation merges two sets by linking the root of one to the root of another if they differ. The parent array tracks these links. Steps show initializing sets, performing unions, and path compression during finds. Key moments clarify why parent pointers update during find and why union only updates one root. Visual quizzes test understanding of parent changes and path compression effects.