Union Find Disjoint Set Data Structure in DSA Python - Cheat Sheet & Quick Revision

Recall & Review

beginner

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

It helps to keep track of elements divided into disjoint sets and efficiently supports two operations: finding which set an element belongs to, and uniting two sets.

beginner

Explain the 'find' operation in Union Find Disjoint Set.

The 'find' operation returns the representative or leader of the set that an element belongs to. It helps to check if two elements are in the same set.

beginner

What does the 'union' operation do in the Union Find Disjoint Set?

The 'union' operation merges two different sets into one by connecting their leaders, so elements from both sets become part of the same set.

intermediate

Why is path compression important in the Union Find Disjoint Set?

Path compression flattens the structure of the tree during 'find' operations by making nodes point directly to the root, which speeds up future 'find' calls.

intermediate

What is union by rank or size and why is it used?

Union by rank or size attaches the smaller tree under the root of the larger tree during union to keep the tree shallow, improving efficiency.

What does the 'find' operation return in a Union Find Disjoint Set?

A The leader or representative of the set

B The size of the set

C The number of sets

D The union of two sets

The 'find' operation returns the leader or representative element of the set that contains the given element.

What is the main goal of the 'union' operation?

A To merge two sets into one

B To delete an element from a set

C To find the size of a set

D To split a set into two

The 'union' operation merges two different sets into a single set.

Which technique helps speed up repeated 'find' operations by flattening the tree?

A Union by size

B Path compression

C Breadth-first search

D Depth-first search

Path compression makes nodes point directly to the root during 'find', speeding up future queries.

Why do we use union by rank or size?

A To delete sets faster

B To increase the height of the tree

C To keep the tree balanced and shallow

D To find the leader faster

Union by rank or size attaches smaller trees under larger ones to keep the tree shallow and efficient.

If two elements have the same leader, what does it mean?

A They belong to different sets

B They are leaders themselves

C They are not connected

D They belong to the same set

If two elements share the same leader, they are in the same set.

Describe how the Union Find Disjoint Set data structure works and its main operations.

Think about how sets are combined and how to check if elements are connected.

Explain the importance of path compression and union by rank/size in optimizing Union Find operations.

Consider how the structure of the sets affects the speed of find and union.

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