Disjoint set (Union-Find) in Data Structures Theory - Step-by-Step Execution

Concept Flow - Disjoint set (Union-Find)

Initialize each element as its own set

↓

Find operation: find root of element

↓

Union operation: merge two sets if roots differ

↓

Repeat find/union as needed

↓

Sets merged

Start with each element separate. Use find to get set leaders. Use union to merge sets by linking leaders.

Execution Sample

Data Structures Theory

parent = [0,1,2,3,4]
rank = [0,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(1,2)
find(2)

Initialize 5 elements, union sets containing 0&1 and 1&2, then find leader of element 2.

Analysis Table

Step	Operation	Parent Array	Rank Array	Action Description	Visual State
1	Initialize	[0,1,2,3,4]	[0,0,0,0,0]	Each element is its own parent	0 1 2 3 4 (all separate)
2	union(0,1)	[0,0,2,3,4]	[1,0,0,0,0]	0 becomes parent of 1, rank[0] increases	0→1 2 3 4
3	union(1,2)	[0,0,0,3,4]	[1,0,0,0,0]	Find roots: 1->0, 2->2; 0 becomes parent of 2	0→1 0→2 3 4
4	find(2)	[0,0,0,3,4]	[1,0,0,0,0]	Find root of 2 is 0	0→1 0→2 3 4
5	Exit	[0,0,0,3,4]	[1,0,0,0,0]	No more operations	0→1 0→2 3 4

💡 All unions done; find confirms root; sets merged accordingly.

State Tracker

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

Key Insights - 3 Insights

Why does union(1,2) update parent of 2 to 0, not 1?

Because find(1) returns 0 as root, union links root of 2 (2) to root of 1 (0), keeping sets connected under root 0 (see step 3 in execution_table).

Why does rank of 0 increase after union(0,1)?

Rank tracks tree height; when 0 becomes parent of 1, its rank increases to reflect taller tree (step 2 in execution_table).

What does find(2) return after unions?

It returns 0, the root of the set containing 2, confirming 2 is connected to 0 (step 4 in execution_table).

Visual Quiz - 3 Questions

Look at the execution_table at step 3, what is the parent of element 2?

A 2

B 1

C 0

D 3

💡 Hint

Check 'Parent Array' column at step 3 in execution_table.

At which step does the rank of element 0 increase?

A Step 1

B Step 2

C Step 3

D Step 4

💡 Hint

Look at 'Rank Array' changes in execution_table between steps 1 and 2.

If we call union(3,4) after step 4, what will be the parent of 4?

A 3

B 0

C 4

D 2

💡 Hint

Union links roots of sets; 3 and 4 are separate sets initially.

Concept Snapshot

Disjoint Set (Union-Find):
- Each element starts as its own parent.
- find(x) returns root parent of x.
- union(x,y) links roots if different.
- Use rank to keep tree shallow.
- Efficient for connectivity queries.

Full Transcript

Disjoint set or Union-Find is a data structure that keeps track of elements partitioned into sets. Each element starts as its own set with itself as parent. The find operation returns the root parent of an element, identifying which set it belongs to. The union operation merges two sets by linking their root parents if they are different. To keep the structure efficient, a rank array tracks tree height and helps decide which root becomes parent during union. This example shows initializing five elements, performing unions on (0,1) and (1,2), and finding the root of element 2, which is 0. The parent and rank arrays update accordingly, merging sets step-by-step.