Path Compression in Union Find in DSA C++

Mental Model

Path compression makes finding the group leader faster by making every node on the path point directly to the leader.

Analogy: Imagine a family tree where each person points to their parent. Path compression is like updating everyone in a branch to point directly to the oldest ancestor, so you can find the ancestor quickly next time.

4 -> 3 -> 1
↑
start (find(4))

After path compression:
4 -> 1
3 -> 1
1 -> 1 (leader)

Dry Run Walkthrough

Input: Union-Find with elements 1 to 4, unions: union(1,2), union(3,4), union(2,4), then find(4)

Goal: Find the leader of element 4 and compress the path so future finds are faster

Step 1: unite(1,2): find leaders of 1 and 2, set parent[2] = 1

parent: [1->1, 2->1, 3->3, 4->4]

Why: Connect 2 to the group led by 1

Step 2: unite(3,4): find leaders of 3 and 4, set parent[4] = 3

parent: [1->1, 2->1, 3->3, 4->3]

Why: Connect 4 to the group led by 3

Step 3: unite(2,4): find(2) returns 1 (path compression keeps 2->1), find(4) returns 3 (path compression keeps 4->3), set parent[3] = 1

parent: [1->1, 2->1, 3->1, 4->3]

Why: Connect group of 4 (leader 3) to group of 2 (leader 1), now 4->3->1

Step 4: find(4): traverse 4->3->1, compress by setting parent[4]=1 and parent[3]=1

parent: [1->1, 2->1, 3->1, 4->1]

Why: Path compression flattens the path during find(4)

Result:

parent: [1->1, 2->1, 3->1, 4->1]
Leader of 4 is 1

Annotated Code

DSA C++

#include <iostream>
#include <vector>
using namespace std;

class UnionFind {
public:
    vector<int> parent;
    UnionFind(int n) {
        parent.resize(n+1);
        for (int i = 1; i <= n; i++) {
            parent[i] = i;
        }
    }

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

    void unite(int a, int b) {
        int rootA = find(a);
        int rootB = find(b);
        if (rootA != rootB) {
            parent[rootB] = rootA; // union by leader
        }
    }

    void printParents(int n) {
        for (int i = 1; i <= n; i++) {
            cout << i << "->" << parent[i] << " ";
        }
        cout << endl;
    }
};

int main() {
    UnionFind uf(4);
    uf.unite(1, 2);
    uf.unite(3, 4);
    uf.unite(2, 4);

    cout << "Parents before find: ";
    uf.printParents(4);

    int leader = uf.find(4);

    cout << "Leader of 4 is " << leader << endl;
    cout << "Parents after find (path compressed): ";
    uf.printParents(4);

    return 0;
}

if (parent[x] != x) { parent[x] = find(parent[x]); }

compress path by making current node point directly to leader

int rootA = find(a); int rootB = find(b);

find leaders of both elements before union

if (rootA != rootB) { parent[rootB] = rootA; }

connect one leader to the other to unify sets

Output

Parents before find: 1->1 2->1 3->1 4->3 

Leader of 4 is 1

Parents after find (path compressed): 1->1 2->1 3->1 4->1 

Complexity Analysis

Time: O(α(n)) amortized per find/union, where α is inverse Ackermann function, almost constant because path compression flattens the tree

Space: O(n) for storing parent array of n elements

vs Alternative: Without path compression, find can be O(n) in worst case; path compression reduces it to almost O(1) amortized

Edge Cases

Single element set

find returns the element itself as leader immediately

DSA C++

if (parent[x] != x) { parent[x] = find(parent[x]); }

Union of already connected elements

No change in parent array, union does nothing

DSA C++

if (rootA != rootB) { parent[rootB] = rootA; }

Find on element with long chain

Path compression flattens chain to direct link to leader

DSA C++

parent[x] = find(parent[x]);

When to Use This Pattern

When you need to quickly find if two elements belong to the same group and merge groups efficiently, use Union Find with path compression to speed up repeated queries.

Common Mistakes

Mistake: Not updating parent during find, so path compression does not happen
Fix: Assign parent[x] = find(parent[x]) inside the find function to compress paths

Mistake: Union without finding leaders first, causing incorrect merges
Fix: Always call find on both elements before union to get their leaders

Summary

It speeds up finding the leader of a group by making nodes point directly to the leader.

Use it when you have many union and find operations on disjoint sets.

The key is to flatten the structure during find so future finds are faster.

Practice

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

easy

A. To merge two sets by size

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

C. To initialize the parent array

D. To count the number of connected components

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 updates nodes along the path to point directly to the root, reducing future search time.

3. Final Answer:

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

4. Quick Check:

   Path compression optimizes find = To speed up the find operation by making nodes point directly to the root [OK]

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

Common Mistakes:

• Confusing path compression with union by size/rank
• Thinking it merges sets instead of optimizing find
• Assuming it initializes data structures

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

easy

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

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

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

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

Solution

1. Step 1: Identify path compression usage

   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 call 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 A

4. Quick Check:

   Path compression requires assignment in recursion = int find(int x) { if(parent[x] != x) parent[x] = find(parent[x]); return parent[x]; } [OK]

Hint: Look for recursive assignment to parent[x] in find [OK]

Common Mistakes:

• Missing assignment to parent[x] for compression
• Using iterative find without compression
• Returning parent[x] without recursion

3. Consider the following code snippet using Union Find with path compression:

int parent[5] = {0, 1, 2, 3, 4};

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

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

unionSet(1, 2);
unionSet(2, 3);
find(3);

What is the state of the parent array after these operations?

medium

A. [0, 1, 3, 3, 4]

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

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

D. [0, 1, 1, 1, 4]

Solution

1. Step 1: Perform unions

   unionSet(1,2): parent[2] = 1; unionSet(2,3): parent[3] = find(2) = 1, so parent[3] = 1.

2. Step 2: Apply find(3) with path compression

   find(3) updates parent[3] to root 1 (already 1), so no change. parent array: [0,1,1,1,4]

3. Final Answer:

   [0, 1, 1, 1, 4] -> Option D

4. Quick Check:

   Parents after unions and compression = [0,1,1,1,4] [OK]

Hint: Trace unions first, then apply find with compression [OK]

Common Mistakes:

• Not updating parent of 3 during union
• Ignoring path compression effect in find
• Confusing indices and values in parent array

4. The following find function is intended to implement path compression but has a bug:

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

What is the bug in this code?

medium

A. It does not update parent[x] during recursion for compression

B. It uses == instead of != in the base case

C. It returns parent[x] instead of x

D. It causes infinite recursion

Solution

1. Step 1: Analyze recursion call

   The recursive call find(parent[x]) is made but its result is not assigned back to parent[x].

2. Step 2: Effect on path compression

   Without assignment, parent[x] remains unchanged, so path compression does not happen.

3. Final Answer:

   It does not update parent[x] during recursion for compression -> Option A

4. Quick Check:

   Missing assignment breaks path compression = It does not update parent[x] during recursion for compression [OK]

Hint: Always assign recursion result to parent[x] for compression [OK]

Common Mistakes:

• Thinking base case condition is wrong
• Assuming return value is incorrect
• Believing it causes infinite recursion

5. You have a Union Find structure with 6 elements (0 to 5). Initially, each element is its own parent. You perform these operations:

unionSet(0, 1);
unionSet(1, 2);
unionSet(3, 4);
unionSet(4, 5);
find(2);
find(5);
unionSet(2, 5);
find(5);

After all operations, what is the parent array state assuming path compression is used in find?

hard

A. [0, 1, 0, 3, 4, 3]

B. [0, 0, 0, 3, 3, 3]

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

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

Solution

1. Step 1: Perform initial unions

   unionSet(0,1): parent[1]=0; unionSet(1,2): parent[2]=find(1)=0; unionSet(3,4): parent[4]=3; unionSet(4,5): parent[5]=find(4)=3;

2. Step 2: Apply finds with path compression

   find(2): compresses path for 2 to 0 (already 0); find(5): compresses path for 5 to 3 (already 3); unionSet(2,5): parent[3]=find(2)=0; find(5): compresses path for 5 to 0, so parent[5]=0;

3. Step 3: Final parent array

   parent[0]=0, parent[1]=0, parent[2]=0, parent[3]=0 (updated), parent[4]=3, parent[5]=0 (compressed)

4. Final Answer:

   [0, 0, 0, 0, 3, 0] -> Option C

5. Quick Check:

   After unions and compression, parent array = [0, 0, 0, 0, 3, 0] [OK]

Hint: Track unions then compress paths after finds [OK]

Common Mistakes:

• Not updating parent of 3 during unionSet(2,5)
• Ignoring path compression effect on 5 after last find
• Mixing parent indices and values