Path Compression in Union Find in DSA C# - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to find the root parent of a node in Union Find.

DSA C#

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

Drag options to blanks, or click blank then click option'

AFind(parent, x)

Bx

Cparent[x]

DFind(parent, parent[x])

Attempts:

3 left

💡 Hint

Common Mistakes

Returning x directly without recursion.

Returning parent[x] without further recursion.

The Find function recursively finds the root parent by calling Find on parent[x].

2fill in blank

medium

Complete the code to perform path compression in the Find function.

DSA C#

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

Drag options to blanks, or click blank then click option'

AFind(parent, parent[x])

BFind(parent, x)

Cx

Dparent[x]

Attempts:

3 left

💡 Hint

Common Mistakes

Assigning parent[x] to x directly.

Assigning parent[x] to parent[x] without recursion.

Path compression sets parent[x] to the root by recursively calling Find on parent[x].

3fill in blank

hard

Fix the error in the Union function to correctly union two sets.

DSA C#

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

Drag options to blanks, or click blank then click option'

Aa

Bb

CrootA

DrootB

Attempts:

3 left

💡 Hint

Common Mistakes

Using a or b instead of their roots.

Setting parent of rootB instead of rootA.

We set parent of rootA to rootB to union the two sets.

4fill in blank

hard

Fill both blanks to implement path compression and return the root.

DSA C#

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

Drag options to blanks, or click blank then click option'

AFind(parent, parent[x])

Bx

Cparent[x]

DFind(parent, x)

Attempts:

3 left

💡 Hint

Common Mistakes

Returning x instead of parent[x].

Not updating parent[x] recursively.

First, update parent[x] to the root by calling Find on parent[x]. Then return parent[x].

5fill in blank

hard

Fill all three blanks to implement Union Find with path compression correctly.

DSA C#

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

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

Drag options to blanks, or click blank then click option'

AFind(parent, parent[x])

BrootA

CrootB

Da

Attempts:

3 left

💡 Hint

Common Mistakes

Not compressing path in Find.

Using wrong variables in Union assignment.

In Find, update parent[x] to root by calling Find on parent[x]. In Union, set parent of rootA to rootB.

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