Union Find Disjoint Set Data Structure in DSA C++ - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Union Find after unions

What is the output of the following C++ code that performs union operations on a Union Find data structure?

DSA C++

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

class UnionFind {
public:
    vector<int> parent, rank;
    UnionFind(int n) {
        parent.resize(n);
        rank.resize(n, 0);
        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 x, int y) {
        int rx = find(x);
        int ry = find(y);
        if (rx != ry) {
            if (rank[rx] < rank[ry]) parent[rx] = ry;
            else if (rank[ry] < rank[rx]) parent[ry] = rx;
            else {
                parent[ry] = rx;
                rank[rx]++;
            }
        }
    }
};

int main() {
    UnionFind uf(5);
    uf.unite(0, 1);
    uf.unite(1, 2);
    uf.unite(3, 4);
    for (int i = 0; i < 5; i++) cout << uf.find(i) << " ";
    return 0;
}

A 0 0 0 3 3

B 1 1 1 4 4

C 0 1 2 3 4

D 0 0 1 3 4

💡 Hint

Remember that union by rank attaches the smaller tree under the root of the deeper tree.

The union operations connect 0,1,2 into one set with root 0, and 3,4 into another set with root 3. The find function returns the root parent for each element.

🧠 Conceptual

intermediate

Number of sets after unions

Given a Union Find data structure initialized with 6 elements (0 to 5), after performing unite(0,1), unite(2,3), unite(4,5), how many disjoint sets remain?

A 4

B 3

C 2

D 1

💡 Hint

Each unite operation merges two sets into one.

Initially, there are 6 sets. Each unite merges two sets, so after 3 unions, 3 sets remain.

🔧 Debug

advanced

Identify the error in Union Find implementation

What error will the following Union Find code produce when calling unite(0,1)?

DSA C++

#include <vector>
using namespace std;

class UnionFind {
public:
    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 find(parent[x]);
        return x;
    }
    void unite(int x, int y) {
        int rx = find(x);
        int ry = find(y);
        if (rx != ry) {
            parent[rx] = ry;
        }
    }
};

int main() {
    UnionFind uf(2);
    uf.unite(0, 1);
    return 0;
}

A Stack overflow due to missing path compression

B Infinite recursion in find function

C No error, code runs correctly

D Segmentation fault due to uninitialized vector

💡 Hint

Check if the find function terminates correctly.

The find function correctly returns the root and terminates. The unite function updates parent correctly. No error occurs.

❓ Predict Output

advanced

Output after path compression

What is the output of the following code after path compression is applied?

DSA C++

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

class UnionFind {
public:
    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 x, int y) {
        int rx = find(x);
        int ry = find(y);
        if (rx != ry) parent[ry] = rx;
    }
};

int main() {
    UnionFind uf(5);
    uf.parent = {0, 0, 1, 2, 3};
    uf.find(4);
    for (int i = 0; i < 5; i++) cout << uf.parent[i] << " ";
    return 0;
}

A 0 0 0 0 0

B 0 0 1 2 3

C 0 1 1 2 3

D 0 0 0 2 3

💡 Hint

Path compression updates all nodes on the path to point directly to the root.

Initially, parent array is {0,0,1,2,3}. Calling find(4) compresses path: 4->3->2->1->0, so all become 0.

🧠 Conceptual

expert

Time complexity of Union Find operations

What is the amortized time complexity of performing m union/find operations on n elements using Union Find with union by rank and path compression?

A O(m)

B O(m log n)

C O(m n)

D O(m α(n)) where α is the inverse Ackermann function

💡 Hint

The inverse Ackermann function grows extremely slowly, almost constant for all practical n.

With union by rank and path compression, the amortized time per operation is almost constant, specifically O(α(n)) where α is the inverse Ackermann function.

Practice

1. What is the primary purpose of the Union Find Disjoint Set data structure?

easy

A. To efficiently track and merge groups of connected elements

B. To sort elements in ascending order

C. To store key-value pairs for fast lookup

D. To implement a queue with priority

Solution

1. Step 1: Understand the role of Union Find

   The Union Find data structure is designed to keep track of which elements belong to which groups or sets, especially when these groups can merge.

2. Step 2: Compare with other data structures

   Sorting elements, storing key-value pairs, or implementing priority queues are different tasks handled by other data structures.

3. Final Answer:

   To efficiently track and merge groups of connected elements -> Option A

4. Quick Check:

   Union Find = Track and merge groups [OK]

Hint: Union Find = track connected groups fast [OK]

Common Mistakes:

• Confusing Union Find with sorting algorithms
• Thinking it stores key-value pairs like a map
• Assuming it manages priority like a heap

2. Which of the following is the correct way to declare a parent array for Union Find of size n in C++?

easy

A. int parent[n+1]; for(int i=1; i<=n; i++) parent[i] = i;

B. int parent[n]; for(int i=0; i

C. int parent[n]; for(int i=0; i<=n; i++) parent[i] = i;

D. int parent[n]; for(int i=1; i

Solution

1. Step 1: Initialize parent array correctly

   The parent array should have size n, and each element should initially be its own parent, so indices 0 to n-1 must be set.

2. Step 2: Check loop boundaries

   Loop must run from 0 to n-1 (i < n) to avoid out-of-bounds errors.

3. Final Answer:

   int parent[n]; for(int i=0; i -> Option B

4. Quick Check:

   Initialize parents from 0 to n-1 [OK]

Hint: Initialize parents from 0 to n-1 [OK]

Common Mistakes:

• Using <= n causing out-of-bounds error
• Starting loop from 1 when array is 0-indexed
• Declaring array size incorrectly

3. Consider the following C++ code using Union Find:

int parent[5];
for(int i=0; i<5; i++) parent[i] = i;

// Union function
void unionSet(int a, int b) {
  int rootA = findSet(a);
  int rootB = findSet(b);
  if(rootA != rootB) parent[rootB] = rootA;
}

// Find function
int findSet(int x) {
  if(parent[x] == x) return x;
  return parent[x] = findSet(parent[x]);
}

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

cout << (findSet(2) == findSet(0)) << " " << (findSet(4) == findSet(0));

What is the output?

medium

A. 0 0

B. 0 1

C. 1 1

D. 1 0

Solution

1. Step 1: Perform unions and find roots

   unionSet(0,1) merges sets of 0 and 1; unionSet(1,2) merges sets of 1 and 2, so 0,1,2 are connected. unionSet(3,4) connects 3 and 4.

2. Step 2: Check if 2 and 0 share the same root, and if 4 and 0 share the same root

   findSet(2) == findSet(0) is true (1), findSet(4) == findSet(0) is false (0).

3. Final Answer:

   1 0 -> Option D

4. Quick Check:

   Connected(2,0) = 1, Connected(4,0) = 0 [OK]

Hint: Check connected sets after unions [OK]

Common Mistakes:

• Assuming 4 is connected to 0
• Forgetting path compression in findSet
• Mixing up union order

4. The following code snippet for Union Find has a bug. What is the error?

int parent[5];
for(int i=0; i<5; i++) parent[i] = i;

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

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

unionSet(0, 1);
unionSet(1, 2);
cout << (findSet(2) == findSet(0));

medium

A. Incorrect initialization of parent array

B. Union function does not check if roots are equal

C. Missing path compression in findSet function

D. Array size is too small for elements

Solution

1. Step 1: Analyze findSet function

   The findSet function recursively finds the root but does not update parent[x] to root, missing path compression optimization.

2. Step 2: Understand impact of missing path compression

   Without path compression, findSet is slower on deep trees but still correct. Other options are incorrect because initialization and union checks are correct, and array size matches elements.

3. Final Answer:

   Missing path compression in findSet function -> Option C

4. Quick Check:

   findSet lacks path compression [OK]

Hint: Check if findSet updates parent for path compression [OK]

Common Mistakes:

• Thinking union lacks root equality check
• Assuming parent array is wrongly initialized
• Confusing array size with element count

5. You have 6 elements (0 to 5) initially in separate sets. After these operations:

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

How many distinct sets remain?

hard

A. 1

B. 2

C. 3

D. 4

Solution

1. Step 1: Track unions step-by-step

   Initially: {0}, {1}, {2}, {3}, {4}, {5} unionSet(0,1) -> {0,1}, {2}, {3}, {4}, {5} unionSet(2,3) -> {0,1}, {2,3}, {4}, {5} unionSet(4,5) -> {0,1}, {2,3}, {4,5} unionSet(1,2) merges {0,1} and {2,3} -> {0,1,2,3}, {4,5} unionSet(0,4) merges {0,1,2,3} and {4,5} -> {0,1,2,3,4,5}

2. Step 2: Count remaining distinct sets

   All elements are connected in one set after last union.

3. Final Answer:

   1 -> Option A

4. Quick Check:

   All merged into one set [OK]

Hint: Count merges to find final distinct sets [OK]

Common Mistakes:

• Counting sets before all unions
• Not merging transitive connections
• Assuming unions only connect pairs