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.

Practice

1. What is the main purpose of a Disjoint Set (Union-Find) data structure?

easy

A. To sort elements in ascending order

B. To store key-value pairs for fast lookup

C. To efficiently keep track of which elements belong to which groups

D. To perform arithmetic calculations on sets

Solution

1. Step 1: Understand the role of Disjoint Set

   Disjoint Set is designed to manage groups of elements and quickly find which group an element belongs to.

2. Step 2: Compare with other options

   Sorting, key-value storage, and arithmetic are unrelated to Disjoint Set's main function.

3. Final Answer:

   To efficiently keep track of which elements belong to which groups -> Option C

4. Quick Check:

   Disjoint Set = group tracking [OK]

Hint: Disjoint Set = fast group membership check [OK]

Common Mistakes:

• Confusing Disjoint Set with sorting algorithms
• Thinking it stores key-value pairs like a dictionary
• Assuming it performs arithmetic on sets

2. Which of the following is the correct way to perform a union operation between two sets containing elements a and b in a Disjoint Set?

easy

A. merge(a, b)

B. union(a, b)

C. unionSet(a, b)

D. combine(a, b)

Solution

1. Step 1: Identify standard Disjoint Set operation names

   The common and standard name for merging two sets is union.

2. Step 2: Check other options

   Other names like unionSet, merge, or combine are not standard and may cause confusion.

3. Final Answer:

   union(a, b) -> Option B

4. Quick Check:

   Union operation = union(a, b) [OK]

Hint: Union operation is always called 'union' [OK]

Common Mistakes:

• Using non-standard method names
• Confusing union with find
• Assuming merge or combine are standard

3. Consider the following sequence of operations on a Disjoint Set with elements {1, 2, 3, 4}:

union(1, 2)
union(3, 4)
union(2, 3)
find(4)

What is the result of find(4)?

medium

A. 4

B. 2

C. 3

D. 1

Solution

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

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

2. Step 2: Find the representative of element 4

   After unions, all elements are in one set. The representative is usually the root of the first union, which is 1.

3. Final Answer:

   1 -> Option D

4. Quick Check:

   find(4) = 1 after unions [OK]

Hint: After unions, find returns the root representative [OK]

Common Mistakes:

• Assuming find(4) returns 4 itself
• Not merging sets correctly in union(2, 3)
• Confusing element with its set representative

4. Given the following incorrect Disjoint Set code snippet, what is the main error?

def union(a, b):
    rootA = find(a)
    rootB = find(b)
    if rootA != rootB:
        rootA = rootB  # Incorrect assignment

medium

A. The assignment does not update the parent of rootA

B. The find function is called incorrectly

C. The union function should return a value

D. The if condition should check rootA == rootB

Solution

1. Step 1: Analyze the union operation

   The union operation should update the parent of one root to the other to merge sets.

2. Step 2: Identify the error in assignment

   Assigning rootA = rootB only changes the local variable, not the parent array that tracks sets.

3. Final Answer:

   The assignment does not update the parent of rootA -> Option A

4. Quick Check:

   Union must update parent array, not local variables [OK]

Hint: Update parent array, not local variables [OK]

Common Mistakes:

• Assigning roots instead of updating parent array
• Confusing equality check in if condition
• Expecting union to return a value

5. You have 5 elements {1, 2, 3, 4, 5} initially in separate sets. After performing union(1, 2), union(3, 4), and union(2, 3), which of the following statements is true?

hard

A. Elements 1 and 4 belong to the same set

B. Element 5 belongs to the same set as element 1

C. Elements 2 and 5 belong to the same set

D. All elements belong to the same set

Solution

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

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

2. Step 2: Check element 5's set

   Element 5 was never unioned, so it remains separate.

3. Final Answer:

   Elements 1 and 4 belong to the same set -> Option A

4. Quick Check:

   1 and 4 connected; 5 separate [OK]

Hint: Only unioned elements share sets; isolated remain separate [OK]

Common Mistakes:

• Assuming all elements merge after some unions
• Thinking element 5 is connected without union
• Confusing which elements are merged