Union Find Disjoint Set Data Structure in DSA C++

Mental Model

Union Find keeps track of which items belong to the same group by linking them together. It quickly tells if two items share a group or not.

Analogy: Imagine a classroom where students form friend groups. Each group has a leader. When two groups merge, one leader becomes the leader of the combined group. To check if two students are friends, you just check if they share the same leader.

0 1 2 3 4 5 6 7 8 9
↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑
Each number is alone, pointing to itself as leader.

Dry Run Walkthrough

Input: Start with 5 elements: 0,1,2,3,4. Perform union(0,1), union(1,2), union(3,4). Check if 0 and 2 are connected, and if 0 and 4 are connected.

Goal: Show how groups merge and how to check if two elements belong to the same group.

Step 1: Initialize each element as its own leader

0->0, 1->1, 2->2, 3->3, 4->4

Why: Each element starts in its own group

Step 2: Union 0 and 1 by making leader of 1 point to leader of 0

0->0, 1->0, 2->2, 3->3, 4->4

Why: 0 and 1 now share the same group led by 0

Step 3: Union 1 and 2 by making leader of 2 point to leader of 0 (found via 1)

0->0, 1->0, 2->0, 3->3, 4->4

Why: 0,1,2 are now in the same group led by 0

Step 4: Union 3 and 4 by making leader of 4 point to leader of 3

0->0, 1->0, 2->0, 3->3, 4->3

Why: 3 and 4 form their own group

Step 5: Check if 0 and 2 are connected by comparing their leaders

0->0, 1->0, 2->0, 3->3, 4->3

Why: Both have leader 0, so connected

Step 6: Check if 0 and 4 are connected by comparing their leaders

0->0, 1->0, 2->0, 3->3, 4->3

Why: Leaders differ (0 vs 3), so not connected

Result:

0->0, 1->0, 2->0, 3->3, 4->3
0 and 2 connected: true
0 and 4 connected: false

Annotated Code

DSA C++

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

class UnionFind {
  vector<int> parent;
  vector<int> rank;
public:
  UnionFind(int n) {
    parent.resize(n);
    rank.resize(n, 0);
    for (int i = 0; i < n; i++) parent[i] = i; // each element is its own leader
  }

  int find(int x) {
    if (parent[x] != x) {
      parent[x] = find(parent[x]); // path compression: link directly to leader
    }
    return parent[x];
  }

  void unite(int x, int y) {
    int rootX = find(x);
    int rootY = find(y);
    if (rootX != rootY) {
      if (rank[rootX] < rank[rootY]) {
        parent[rootX] = rootY; // attach smaller tree under bigger
      } else if (rank[rootX] > rank[rootY]) {
        parent[rootY] = rootX;
      } else {
        parent[rootY] = rootX;
        rank[rootX]++; // increase rank if same
      }
    }
  }

  bool connected(int x, int y) {
    return find(x) == find(y); // true if same leader
  }

  void printParents() {
    for (int i = 0; i < parent.size(); i++) {
      cout << i << "->" << parent[i];
      if (i != parent.size() - 1) cout << ", ";
    }
    cout << endl;
  }
};

int main() {
  UnionFind uf(5);
  uf.printParents();
  uf.unite(0, 1);
  uf.printParents();
  uf.unite(1, 2);
  uf.printParents();
  uf.unite(3, 4);
  uf.printParents();
  cout << boolalpha;
  cout << "0 and 2 connected: " << uf.connected(0, 2) << endl;
  cout << "0 and 4 connected: " << uf.connected(0, 4) << endl;
  return 0;
}

for (int i = 0; i < n; i++) parent[i] = i; // each element is its own leader

initialize each element as its own leader

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

path compression: link element directly to leader to speed future finds

int rootX = find(x); int rootY = find(y);

find leaders of both elements

if (rootX != rootY) { ... }

only unite if leaders differ to merge groups

if (rank[rootX] < rank[rootY]) { parent[rootX] = rootY; } else if ...

attach smaller tree under bigger to keep tree shallow

return find(x) == find(y);

check if two elements share the same leader

Output

0->0, 1->1, 2->2, 3->3, 4->4

0->0, 1->0, 2->2, 3->3, 4->4

0->0, 1->0, 2->0, 3->3, 4->4

0->0, 1->0, 2->0, 3->3, 4->3

0 and 2 connected: true

0 and 4 connected: false

Complexity Analysis

Time: O(α(n)) per operation, where α is the inverse Ackermann function, practically constant, because path compression and union by rank keep trees flat

Space: O(n) for storing parent and rank arrays for n elements

vs Alternative: Naive union-find without path compression or rank can degrade to O(n) per operation, making this optimized approach much faster

Edge Cases

Union or find on single element

Element is its own leader, operations return quickly

DSA C++

for (int i = 0; i < n; i++) parent[i] = i; // each element is its own leader

Union of already connected elements

No changes happen, avoids cycles

DSA C++

if (rootX != rootY) { ... }

Find on element with deep chain

Path compression flattens chain for future fast access

DSA C++

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

When to Use This Pattern

When you need to quickly group items and check if two items belong to the same group, use Union Find because it efficiently merges groups and checks connectivity.

Common Mistakes

Mistake: Not using path compression causing slow find operations
Fix: Add path compression by updating parent[x] during find to point directly to leader

Mistake: Not checking if leaders differ before union causing incorrect merges
Fix: Only unite if leaders are different to avoid cycles

Summary

It groups elements into sets and quickly checks if two elements are in the same set.

Use it when you need to manage dynamic connectivity or grouping problems.

The key is to keep track of leaders and flatten the structure for fast queries.

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