Path Compression in Union Find in DSA C++ - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of find operation with path compression

What is the output of the following C++ code snippet that uses path compression in Union Find?

DSA C++

class UnionFind {
public:
    std::vector<int> parent;
    UnionFind(int n) {
        parent.resize(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 unite(int a, int b) {
        int rootA = find(a);
        int rootB = find(b);
        if (rootA != rootB) {
            parent[rootB] = rootA;
        }
    }
};

int main() {
    UnionFind uf(5);
    uf.unite(0, 1);
    uf.unite(1, 2);
    uf.unite(3, 4);
    int root = uf.find(2);
    std::string result = "parent array: ";
    for (int i = 0; i < 5; i++) {
        result += std::to_string(uf.parent[i]) + " ";
    }
    std::cout << result << std::endl;
    std::cout << "root of 2: " << root << std::endl;
    return 0;
}

A parent array: 0 0 1 3 4 \nroot of 2: 0

B parent array: 0 0 0 3 3 \nroot of 2: 0

C parent array: 0 1 1 3 3 \nroot of 2: 1

D parent array: 0 0 0 4 4 \nroot of 2: 0

💡 Hint

Remember that path compression updates the parent of all nodes on the path to the root.

After uniting 0-1 and 1-2, all three nodes 0,1,2 share the same root 0. The find(2) call compresses the path, making parent[2] point directly to 0. The parent array reflects this with parent[0]=0, parent[1]=0, parent[2]=0, and the other sets unchanged.

🧠 Conceptual

intermediate

Effect of path compression on find operation

Which of the following best describes the effect of path compression in the find operation of Union Find?

A It flattens the tree by making every node on the path point directly to the root, speeding up future finds.

B It increases the height of the tree by adding extra nodes to the path.

C It removes nodes from the tree to reduce its size.

D It swaps the parents of two nodes to balance the tree.

💡 Hint

Think about how path compression changes the parent links during find.

Path compression makes all nodes on the find path point directly to the root, flattening the structure and making future find operations faster.

🔧 Debug

advanced

Identify the error in this Union Find implementation with path compression

What error will the following code produce when calling find(2)?

DSA C++

class UnionFind {
public:
    std::vector<int> parent;
    UnionFind(int n) {
        parent.resize(n);
        for (int i = 0; i < n; i++) parent[i] = i;
    }
    int find(int x) {
        if (parent[x] == x) {
            return x;
        }
        return parent[x] = find(parent[x]);
    }
};

int main() {
    UnionFind uf(3);
    uf.parent = {0, 0, 1};
    int root = uf.find(2);
    std::cout << "root: " << root << std::endl;
    return 0;
}

A Compilation error due to missing return statement in find

B Runtime error: stack overflow due to infinite recursion

C Output: root: 0

D Output: root: 2

💡 Hint

Check if all code paths in find return a value.

The find function lacks a return statement after the recursive call, causing a compilation error.

❓ Predict Output

advanced

Final parent array after multiple unions and finds with path compression

What is the final state of the parent array after the following operations?

DSA C++

class UnionFind {
public:
    std::vector<int> parent;
    UnionFind(int n) {
        parent.resize(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 unite(int a, int b) {
        int rootA = find(a);
        int rootB = find(b);
        if (rootA != rootB) {
            parent[rootB] = rootA;
        }
    }
};

int main() {
    UnionFind uf(6);
    uf.unite(0, 1);
    uf.unite(1, 2);
    uf.unite(3, 4);
    uf.unite(4, 5);
    uf.find(5);
    uf.unite(2, 5);
    uf.find(5);
    std::string result = "parent array: ";
    for (int i = 0; i < 6; i++) {
        result += std::to_string(uf.parent[i]) + " ";
    }
    std::cout << result << std::endl;
    return 0;
}

A parent array: 0 0 0 0 0 0

B parent array: 0 0 0 3 3 3

C parent array: 0 0 0 0 3 0

D parent array: 0 1 0 3 3 3

💡 Hint

Remember that find with path compression updates parents along the path.

After all unions and finds, the entire set is connected with root 0. Path compression updates parent[3] and parent[5] to 0, making the parent array: 0 0 0 0 3 0.

🧠 Conceptual

expert

Time complexity impact of path compression in Union Find

What is the amortized time complexity of a find operation with path compression in a Union Find data structure?

A O(log n) worst case per operation

B O(n log n) for all operations combined

C O(n) per operation in worst case

D O(1) amortized, almost constant time

💡 Hint

Path compression flattens the tree structure over time.

With path compression, the amortized time per find operation is almost constant, often described as inverse Ackermann function, which is very slow growing and practically constant.

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