Path Compression in Union Find in DSA C - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the main purpose of path compression in Union Find?

Path compression helps to speed up the 'find' operation by making nodes on the path point directly to the root, flattening the structure for faster future queries.

beginner

In Union Find, what does the 'find' function return after path compression?

It returns the root or representative of the set, and updates all nodes on the path to point directly to this root.

intermediate

How does path compression affect the time complexity of Union Find operations?

It reduces the amortized time complexity of 'find' and 'union' operations to nearly O(1), specifically O(α(n)) where α is the inverse Ackermann function, which grows very slowly.

beginner

Show the basic idea of path compression in code form for the 'find' function.

int find(int x) { if (parent[x] != x) { parent[x] = find(parent[x]); // Path compression step } return parent[x]; }

intermediate

Why is path compression important in real-life applications of Union Find?

Because it makes repeated queries about connectivity or grouping very fast, which is useful in network connectivity, image processing, and clustering problems.

What does path compression do in the Union Find data structure?

A Makes every node on the find path point directly to the root

B Merges two sets by size

C Deletes nodes from the set

D Splits sets into smaller subsets

Path compression updates nodes on the path to point directly to the root, speeding up future find operations.

Which function is directly improved by path compression?

A Union

B Insert

C Find

D Delete

Path compression optimizes the 'find' function by flattening the tree structure.

What is the typical time complexity of Union Find operations with path compression?

A O(n)

B O(α(n)) (inverse Ackermann function)

C O(n^2)

D O(log n)

With path compression, the amortized time complexity is nearly constant, O(α(n)), which is very efficient.

In the code snippet for find with path compression, what happens when parent[x] != x?

A We recursively find the root and update parent[x]

B We return x immediately

C We do nothing

D We delete x

If x is not the root, we recursively find the root and update parent[x] to point directly to it.

Why is path compression combined with union by rank or size?

A To make the tree taller

B To slow down the union operation

C To increase memory usage

D To keep the tree shallow and speed up operations

Combining path compression with union by rank or size keeps the tree shallow, making operations faster.

Explain how path compression works in the Union Find data structure and why it improves performance.

Think about what happens to nodes on the path when you find the root.

Describe the difference between a Union Find without path compression and one with path compression in terms of structure and speed.

Consider how the parent pointers change after multiple find operations.

Practice

1. What is the main purpose of path compression in the Union Find data structure?

easy

A. To initialize the parent array

B. To merge two sets by size

C. To count the number of connected components

D. To speed up the find operation by making nodes point directly to the root

Solution

1. Step 1: Understand the find operation

   The find operation locates the root parent of a node in Union Find.

2. Step 2: Role of path compression

   Path compression makes all nodes on the path point directly to the root, speeding up future find calls.

3. Final Answer:

   To speed up the find operation by making nodes point directly to the root -> Option D

4. Quick Check:

   Path compression optimizes find = C [OK]

Hint: Path compression flattens tree for faster find [OK]

Common Mistakes:

• Confusing path compression with union by size
• Thinking it initializes the structure
• Believing it counts components

2. Which of the following is the correct syntax for the find function with path compression in C?

easy

A. int find(int x) { while(parent[x] != x) x = parent[x]; return x; }

B. int find(int x) { if(parent[x] != x) parent[x] = find(parent[x]); return parent[x]; }

C. int find(int x) { if(parent[x] == x) return x; else return find(parent[x]); }

D. int find(int x) { parent[x] = x; return x; }

Solution

1. Step 1: Identify path compression in code

   Path compression updates parent[x] during recursion to root.

2. Step 2: Check each option

   int find(int x) { if(parent[x] != x) parent[x] = find(parent[x]); return parent[x]; } updates parent[x] with recursive find result, implementing path compression correctly.

3. Final Answer:

   int find(int x) { if(parent[x] != x) parent[x] = find(parent[x]); return parent[x]; } -> Option B

4. Quick Check:

   Path compression updates parent recursively = A [OK]

Hint: Look for parent update inside find recursion [OK]

Common Mistakes:

• Using loop without updating parent (Option B)
• Not updating parent during recursion (Option C)
• Resetting parent incorrectly (Option D)

3. Given the following Union Find structure with parent = [0, 0, 1, 2, 3], what will be the parent array after calling find(4) with path compression?

medium

A. [0, 0, 0, 0, 0]

B. [0, 0, 1, 2, 0]

C. [0, 1, 1, 2, 3]

D. [0, 0, 1, 3, 3]

Solution

1. Step 1: Trace find(4) path

   4's parent is 3, 3's parent is 2, 2's parent is 1, 1's parent is 0, which is root.

2. Step 2: Apply path compression

   All nodes on path (4,3,2,1) update parent to root 0 (parent[1] already 0). parent[2]=0, parent[3]=0, parent[4]=0. So parent array becomes [0,0,0,0,0].

3. Final Answer:

   [0, 0, 0, 0, 0] -> Option A

4. Quick Check:

   Path compression sets parent[4] = 0 = A [OK]

Hint: Update all parents on path to root after find [OK]

Common Mistakes:

• Only updating parent[4] to root (Option B)
• Not updating any parent (Option C)
• Updating wrong parents (Option D)

4. Identify the bug in this find function with path compression:

int find(int x) {
  if(parent[x] == x) return x;
  else {
    find(parent[x]);
    parent[x] = parent[parent[x]];
    return parent[x];
  }
}

medium

A. No bug, code is correct

B. Incorrect base case condition

C. Missing return value from recursive call before assignment

D. Parent update should be after return

Solution

1. Step 1: Analyze recursive call

   The recursive call find(parent[x]) is made but its return value is ignored.

2. Step 2: Check parent update

   Parent update uses parent[parent[x]] instead of the root returned by recursion, so path compression fails.

3. Final Answer:

   Missing return value from recursive call before assignment -> Option C

4. Quick Check:

   Return value must be assigned to parent[x] = D [OK]

Hint: Assign recursive find result to parent[x] for compression [OK]

Common Mistakes:

• Ignoring recursive return value
• Updating parent incorrectly
• Misunderstanding base case

5. You have a Union Find with 5 elements and parent = [0, 0, 1, 2, 3]. After calling union(4, 0) and then find(4) with path compression, what is the final parent array?

hard

A. [0, 0, 1, 2, 0]

B. [0, 0, 1, 2, 4]

C. [0, 0, 0, 0, 0]

D. [0, 1, 1, 2, 0]

Solution

1. Step 1: Perform union(4, 0)

   Find roots: root(4) = 4 (chain 4->3->2->1->0), root(0) = 0. Since roots differ, link root(4) to root(0). So parent[4] = 0. Updated parent = [0, 0, 1, 2, 0].

2. Step 2: Call find(4) with path compression

   Path: 4 -> 0. Since 0 is root, parent[4] already 0, no further updates. Final parent = [0, 0, 1, 2, 0].

3. Final Answer:

   [0, 0, 1, 2, 0] -> Option A

4. Quick Check:

   Union links 4 to 0, find compresses path = A [OK]

Hint: Union links roots, find compresses path to root [OK]

Common Mistakes:

• Incorrectly linking assuming same root (Option C)
• Wrong union target (Option B)
• Incomplete path compression (Option D)