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 simple Union Find data structure with path compression to quickly find the leader (representative) of each friend group.

📋 What You'll Learn

Create an integer array called parent representing each person's parent in the friend group.

Create an integer variable called n to represent the total number of people.

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

Write a method Union to merge two friend groups.

Print the parent array after some unions to show the compressed paths.

💡 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 is important for software engineers working on graph algorithms, network design, and optimization problems.

1

Create the parent array for 5 people

Create an integer variable called n and set it to 5. Then create an integer array called parent of size n where each element is initialized to its own index (0 to 4).

DSA C#

// Create n and parent array where each person is their own parent
// Your code here

Hint

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

2

Write the Find method with path compression

Write a method 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 n = 5;
int[] parent = new int[n];
for (int i = 0; i < n; i++)
{
    parent[i] = i;
}

// Write the Find method with path compression below
// Your code here

Hint

Use recursion to find the leader and update parent[x] to compress the path.

3

Write the Union method to merge two groups

Write a method called Union that takes two integers a and b. Find their leaders using Find. If the leaders are different, set the parent of b's leader to a's leader to merge the groups.

DSA C#

int n = 5;
int[] parent = new int[n];
for (int i = 0; i < n; i++)
{
    parent[i] = i;
}

int Find(int x)
{
    if (parent[x] != x)
    {
        parent[x] = Find(parent[x]);
    }
    return parent[x];
}

// Write the Union method below
// Your code here

Hint

Use Find to get leaders and update the parent of one leader to the other.

4

Perform unions and print the parent array

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

DSA C#

int n = 5;
int[] parent = new int[n];
for (int i = 0; i < n; i++)
{
    parent[i] = i;
}

int Find(int x)
{
    if (parent[x] != x)
    {
        parent[x] = Find(parent[x]);
    }
    return parent[x];
}

void Union(int a, int b)
{
    int rootA = Find(a);
    int rootB = Find(b);
    if (rootA != rootB)
    {
        parent[rootB] = rootA;
    }
}

// Call Union methods and print the parent array below
// Your code here

Hint

After unions, print the parent array elements separated by spaces on one line.

Practice

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

easy

A. To speed up the find operation by flattening the tree

B. To merge two sets without checking their roots

C. To delete elements from the set efficiently

D. To sort the elements in each set

Solution

1. Step 1: Understand the role of path compression

   Path compression is used during the find operation to make future queries faster by making nodes point directly to the root.

2. Step 2: Identify the effect on the tree structure

   This flattens the tree, reducing the height and speeding up subsequent find calls.

3. Final Answer:

   To speed up the find operation by flattening the tree -> Option A

4. Quick Check:

   Path compression = flatten tree = faster find [OK]

Hint: Path compression flattens trees to speed up find [OK]

Common Mistakes:

• Thinking path compression merges sets
• Confusing path compression with union by rank
• Believing it deletes elements

2. Which of the following is the correct syntax for the find method 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) { return parent[x]; }

C. int Find(int x) { if (parent[x] != x) parent[x] = Find(parent[x]); return parent[x]; }

D. int Find(int x) { if (parent[x] == x) return x; else return Find(x); }

Solution

1. Step 1: Check for path compression in the code

   int Find(int x) { if (parent[x] != x) parent[x] = Find(parent[x]); return parent[x]; } updates parent[x] to the root during recursion, which is path compression.

2. Step 2: Verify other options

   int Find(int x) { while (parent[x] != x) x = parent[x]; return x; } uses a loop but does not update parents. int Find(int x) { return parent[x]; } returns parent directly without recursion. int Find(int x) { if (parent[x] == x) return x; else return Find(x); } causes infinite recursion.

3. Final Answer:

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

4. Quick Check:

   Path compression updates parent during find [OK]

Hint: Look for recursive parent update in find method [OK]

Common Mistakes:

• Using loop without updating parents
• Returning parent without recursion
• Infinite recursion by calling Find(x) instead of Find(parent[x])

3. Given the following code snippet, what will be the output after calling uf.Find(3)?

var uf = new UnionFind(5);
uf.Union(1, 2);
uf.Union(2, 3);
Console.WriteLine(uf.Find(3));

Assume Union merges sets by attaching root of second to first and Find uses path compression.

medium

A. 2

B. 1

C. 3

D. 4

Solution

1. Step 1: Trace the unions

   Union(1,2) makes 1 the root of 2. Union(2,3) attaches 3 under 2, so root of 3 is 1 through 2.

2. Step 2: Find root of 3 with path compression

   Find(3) follows parent chain 3 -> 2 -> 1, returns 1 and compresses path so 3 points directly to 1.

3. Final Answer:

   1 -> Option B

4. Quick Check:

   Root after unions = 1 [OK]

Hint: Follow parent chain after unions to find root [OK]

Common Mistakes:

• Assuming root is 3 or 2 without tracing
• Ignoring path compression effect
• Confusing union direction

4. Identify the bug in this Find method implementation with path compression:

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

medium

A. It should use a loop instead of recursion

B. It does not return the root correctly

C. It does not perform path compression

D. It causes infinite recursion because it calls Find(x) instead of Find(parent[x])

Solution

1. Step 1: Analyze the recursive call

   The method calls Find(x) again without changing x, causing infinite recursion.

2. Step 2: Correct recursive call for path compression

   It should call Find(parent[x]) to move up the tree and compress paths.

3. Final Answer:

   It causes infinite recursion because it calls Find(x) instead of Find(parent[x]) -> Option D

4. Quick Check:

   Recursive call must use parent[x] [OK]

Hint: Recursive find must call Find(parent[x]) not Find(x) [OK]

Common Mistakes:

• Calling Find(x) again causes infinite loop
• Forgetting to update parent for compression
• Using loop but missing path compression

5. You have a Union Find with 6 elements (0 to 5). After these operations:

uf.Union(0, 1);
uf.Union(1, 2);
uf.Union(3, 4);
uf.Union(4, 5);
uf.Find(2);
uf.Find(5);
uf.Union(2, 5);
uf.Find(5);

How many elements will directly point to the root of their set after all operations with path compression?

hard

A. 6

B. 4

C. 3

D. 2

Solution

1. Step 1: Track unions and finds

   Unions create two sets: {0,1,2} and {3,4,5}. Finds on 2 and 5 compress paths so 0 and 3 become roots with direct children.

2. Step 2: After union(2,5) and find(5), all nodes in one set with path compression

   After union(2,5), sets merge. Find(5) compresses path so nodes 2 and 5 point directly to root. Nodes 0 and 1 also point to root from earlier compression.

3. Step 3: Count elements directly pointing to root

   Elements 0,1,2,3,4,5 all point directly to the root after the final find(5) call due to path compression.

4. Final Answer:

   6 -> Option A

5. Quick Check:

   All nodes point directly to root after final find call [OK]

Hint: Count nodes updated by find calls for direct root pointers [OK]

Common Mistakes:

• Assuming all nodes point directly after union
• Ignoring path compression effect only on find calls
• Counting nodes without tracing parent updates