Path Compression in Union Find in DSA C - Build from Scratch

Path Compression in Union Find

📖 Scenario: Imagine you are managing a social network where people form friend groups. You want to quickly find out if two people are in the same friend group and efficiently merge groups when new friendships form.

🎯 Goal: You will build a Union Find data structure with path compression to quickly find the leader (representative) of each friend group. This helps speed up queries about group membership.

📋 What You'll Learn

Create an array called parent to represent each person's group leader.

Create an integer variable n for the number of people.

Write a function find that uses path compression to find the leader of a person.

Write a function union_sets to merge two groups by connecting their leaders.

Print the parent array after some union operations to show the final group leaders.

💡 Why This Matters

🌍 Real World

Union Find with path compression is used in social networks, network connectivity, and clustering to quickly find connected components.

💼 Career

Understanding Union Find helps in solving problems related to grouping, connectivity, and efficient query handling in software engineering and competitive programming.

1

Create the parent array for 5 people

Create an integer variable n and set it to 5. Then create an integer array called parent of size n. Initialize each element of parent so that parent[i] = i for i from 0 to n-1.

DSA C

int n = 5;
int parent[5];
// Initialize parent array so that parent[i] = i
// Your code here

Hint

Use a for loop from 0 to n-1 and set parent[i] to i.

2

Write the find function with path compression

Write a function called find that takes an integer x and returns the leader of x. Use path compression by setting parent[x] to the result of find(parent[x]) when x is not its own parent.

DSA C

int find(int x) {
    // Your code here
}

Hint

Check if x is its own parent. If not, update parent[x] by calling find recursively.

3

Write the union_sets function to merge two groups

Write a function called union_sets that takes two integers a and b. Find their leaders using find. If the leaders are different, set the parent of leader of a to the leader of b.

DSA C

void union_sets(int a, int b) {
    // Your code here
}

Hint

Find leaders of both elements. If different, connect one leader to the other.

4

Perform unions and print the parent array

Call union_sets(0, 1), union_sets(1, 2), and union_sets(3, 4). Then print the parent array elements separated by spaces on one line.

DSA C

// Perform unions and print parent array below
// Your code here

Hint

Call the union functions as instructed. Then print each element of parent with a space.

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)