Disjoint set (Union-Find) in Data Structures Theory - Full Explanation

Introduction

Imagine you have many groups of friends, and you want to quickly find out if two people are in the same group or not. Managing these groups efficiently is tricky when they keep merging. Disjoint set, also called Union-Find, solves this problem by keeping track of which elements belong together and allowing fast merging and checking.

Explanation

Sets and Elements

The disjoint set structure manages multiple groups, called sets, where each element belongs to exactly one set. Initially, every element is in its own set, separate from others. This setup helps in tracking which elements are connected or grouped together.

Each element starts in its own unique set, ensuring no overlaps.

Find Operation

The find operation helps identify which set an element belongs to by returning a representative or leader of that set. This representative acts like a name tag for the whole group. It allows us to quickly check if two elements share the same set by comparing their representatives.

Find returns the set's representative to identify group membership.

Union Operation

Union merges two different sets into one, combining their elements under a single representative. This operation is used when we discover a connection between elements from separate sets. Efficient union keeps the structure balanced to speed up future operations.

Union combines two sets into one, updating their representative.

Path Compression

Path compression is a technique used during the find operation to speed up future searches. It flattens the structure by making elements point directly to the set representative. This reduces the time needed to find the representative in later operations.

Path compression speeds up find by flattening the set structure.

Union by Rank/Size

To keep the sets balanced, union by rank or size attaches the smaller set under the larger one. This prevents the structure from becoming too tall, which would slow down find operations. It helps maintain efficient performance even after many unions.

Union by rank or size keeps the sets balanced for efficiency.

Real World Analogy

Imagine a school where each student starts in their own club. When two clubs decide to join forces, they pick one leader to represent the new combined club. To find out which club a student belongs to, you ask who their leader is. Over time, students remember their leader directly, making it faster to find their club.

Sets and Elements → Each student starting in their own club

Find Operation → Asking a student who their club leader is

Union Operation → Two clubs merging and choosing one leader

Path Compression → Students remembering their leader directly to avoid asking others

Union by Rank/Size → Smaller club joining the bigger club to keep things simple

Diagram

Diagram

Initial sets:
 1   2   3   4
  |   |   |   |
[1] [2] [3] [4]

After union(1,2):
 1       3   4
 |       |   |
[1]---->[2] [3] [4]

After union(3,4):
 1       3
 |       |
[1]---->[2] [3]---->[4]

After union(2,3):
 1
 |
[1]---->[2]---->[3]---->[4]

Find with path compression flattens:
 1
 |
[1]---->[2]
  |      |
  +---->[3]
         |
        [4]

This diagram shows sets as chains of elements pointing to their representative, illustrating unions and path compression flattening.

Key Facts

Disjoint Set → A data structure that keeps track of elements partitioned into non-overlapping sets.

Find Operation → Returns the representative element of the set containing a given element.

Union Operation → Merges two distinct sets into a single set.

Path Compression → An optimization that flattens the structure during find to speed up future queries.

Union by Rank/Size → An optimization that attaches the smaller set under the larger to keep the tree shallow.

Code Example

Data Structures Theory

class DisjointSet:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])  # Path compression
        return self.parent[x]

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

# Example usage
ds = DisjointSet(5)  # Elements 0 to 4

# Initially, all are separate
print(ds.find(0))  # 0
print(ds.find(1))  # 1

# Union sets containing 0 and 1
 ds.union(0, 1)
print(ds.find(0))  # Same as find(1)
print(ds.find(1))  # Same as find(0)

# Union sets containing 3 and 4
 ds.union(3, 4)
print(ds.find(3))  # Same as find(4)

# Union sets containing 1 and 3 (merging two groups)
 ds.union(1, 3)
print(ds.find(0))  # Same representative for 0,1,3,4
print(ds.find(4))  # Same representative for 0,1,3,4

Common Confusions

Thinking that find returns the actual element instead of the set representative.

Thinking that find returns the actual element instead of the set representative. Find returns the leader or representative of the set, which may be different from the element itself.

Believing union always merges sets by simply linking any element.

Believing union always merges sets by simply linking any element. Union carefully merges sets by rank or size to keep the structure efficient, not just by linking any elements.

Assuming path compression changes the set membership.

Assuming path compression changes the set membership. Path compression only changes pointers to speed up find; it does not alter which elements belong to which sets.

Summary

Disjoint set (Union-Find) helps manage groups of elements that merge over time and lets you quickly check if two elements are in the same group.

The find operation returns a group's representative, while union merges two groups efficiently using rank or size to keep the structure balanced.

Path compression speeds up repeated find operations by flattening the structure, making future queries faster.

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