Union Find Disjoint Set Data Structure in DSA C++ - Deep Dive

Overview - Union Find Disjoint Set Data Structure

What is it?

Union Find Disjoint Set is a data structure that keeps track of a group of elements split into separate sets. It supports two main operations: finding which set an element belongs to, and merging two sets into one. This helps quickly answer questions like whether two elements are connected or in the same group. It is often used in problems involving grouping, connectivity, and network components.

Why it matters

Without Union Find, checking if elements belong to the same group or merging groups would be slow and complicated, especially when dealing with many elements and operations. This data structure makes these operations very fast, enabling efficient solutions to real-world problems like social networks, computer networks, and clustering. It saves time and resources by avoiding repeated full searches.

Where it fits

Before learning Union Find, you should understand basic arrays and simple data structures. After mastering it, you can explore graph algorithms like Kruskal's Minimum Spanning Tree and connected components. It also leads to advanced topics like dynamic connectivity and offline query processing.

Mental Model

Core Idea

Union Find keeps track of which elements belong together by linking them in groups and quickly finding the group's representative.

Think of it like...

Imagine a classroom where students form friend groups. Each group has a leader who represents the group. When two groups become friends, their leaders agree to merge the groups under one leader. To check if two students are in the same friend group, you just ask who their leaders are.

Sets represented by trees:

  1       4       7
  |       |       |
  2       5       8
  |               |
  3               9

Each tree root is the group's leader (representative).
Operations:
- Find: climb up to the root leader.
- Union: connect one root to another to merge groups.

Build-Up - 7 Steps

1

Foundation

Basic structure and initialization

Concept: Introduce the array-based structure to represent each element's parent and initialize each element as its own leader.

We use an array called parent where parent[i] stores the leader of element i. Initially, each element is its own leader, so parent[i] = i for all i. This means every element starts in its own set.

Result

parent array after initialization for 5 elements: [0, 1, 2, 3, 4]

Understanding that each element starts as a separate group sets the foundation for merging and finding groups efficiently.

2

Foundation

Find operation to identify group leader

Concept: Learn how to find the leader (representative) of the set an element belongs to by following parent links.

To find the leader of element x, we check parent[x]. If parent[x] == x, x is the leader. Otherwise, we recursively find the leader of parent[x]. This climbs up the tree until the root leader is found.

Result

Find(3) returns 3 if parent[3] = 3; if parent[3] = 2 and parent[2] = 2, Find(3) returns 2.

Knowing how to find the leader allows us to quickly check if two elements belong to the same group.

3

Intermediate

Union operation to merge sets

🤔Before reading on: When merging two sets, do you think we should always attach the second set to the first, or choose based on size? Commit to your answer.

Concept: Combine two sets by linking the leader of one set to the leader of the other, effectively merging their groups.

To union sets containing elements x and y, find their leaders rootX and rootY. If they differ, set parent[rootX] = rootY to merge. This connects one group's leader to the other, making them one group.

Result

After union(1, 2), parent might look like [0, 2, 2, 3, 4], meaning 1 and 2 share leader 2, and 3 is separate.

Merging groups by leaders keeps the structure simple and allows quick future queries about group membership.

4

Intermediate

Path compression optimization

🤔Before reading on: Do you think updating parent links during find helps speed up future finds? Commit to yes or no.

Concept: Improve find operation by making every element on the path point directly to the leader, flattening the tree.

During find(x), after finding the leader, update parent[x] to point directly to the leader. This reduces the tree height, making future finds faster.

Result

After find(3) with path compression, parent might change from [0,1,2,2,4] to [0,1,2,2,4] but with direct links for deeper trees.

Path compression drastically reduces the time complexity of find operations, making the data structure almost constant time per operation.

5

Intermediate

Union by rank or size

🤔Before reading on: Should we attach smaller trees under bigger ones or vice versa? Commit to your answer.

Concept: Keep track of tree sizes or ranks to attach smaller trees under bigger ones, preventing tall trees.

Maintain an array rank or size. When unioning, attach the root of the smaller tree to the root of the bigger tree. Update rank or size accordingly.

Result

Union by rank keeps trees shallow, improving find efficiency. For example, union(1,2) attaches smaller rank tree under bigger rank tree.

Balancing trees during union prevents performance degradation, ensuring operations stay efficient even after many merges.

6

Advanced

Amortized analysis and complexity

🤔Before reading on: Do you think Union Find operations are constant time or logarithmic time on average? Commit to your answer.

Concept: Understand that with path compression and union by rank, operations run in nearly constant time, called inverse Ackermann function time.

The combination of path compression and union by rank makes find and union operations run in O(α(n)) time, where α(n) is a very slow-growing function, practically constant for all reasonable n.

Result

This means even millions of union/find operations run very fast in practice.

Knowing the near-constant time complexity explains why Union Find is preferred for large-scale connectivity problems.

7

Expert

Persistent and dynamic Union Find variants

🤔Before reading on: Can Union Find be adapted to support undo operations or dynamic connectivity? Commit to yes or no.

Concept: Explore advanced versions that allow undoing unions or handling changes over time, useful in complex applications.

Persistent Union Find stores history to revert unions. Dynamic connectivity structures extend Union Find to handle edge insertions and deletions efficiently. These require more complex data structures and algorithms.

Result

These variants enable solving problems like offline queries, rollback operations, and dynamic network changes.

Understanding these advanced forms reveals the flexibility and depth of Union Find beyond basic use cases.

Under the Hood

Internally, Union Find uses arrays to represent a forest of trees where each tree represents a set. Each element points to its parent, and the root is the leader. Find operations traverse parent links to find the root. Union operations link roots to merge trees. Path compression flattens trees by making nodes point directly to roots during find. Union by rank or size keeps trees balanced by attaching smaller trees under larger ones. This combination ensures very shallow trees and fast operations.

Why designed this way?

The design balances simplicity and efficiency. Arrays provide fast access and updates. Trees represent sets naturally. Path compression and union by rank were introduced to avoid worst-case tall trees that slow down operations. Alternatives like linked lists or hash sets are slower for repeated union/find queries. The chosen design optimizes for many union/find operations, common in graph and network problems.

Union Find internal structure:

  Elements: 0 1 2 3 4
  Parent:   0 0 1 1 4

Trees:
  0
  ├─1
  │ ├─2
  │ └─3
  4

Find(3): climb 3 -> 1 -> 0 (leader)
Union(4,0): parent[4] = 0

After union:
  0
  ├─1
  │ ├─2
  │ └─3
  └─4

Myth Busters - 4 Common Misconceptions

Quick: Does union always merge the smaller set into the bigger one? Commit to yes or no.

Common Belief: Union always merges the smaller set into the bigger set automatically.

Reality: Union merges sets based on rank or size only if implemented; otherwise, it may merge arbitrarily, causing tall trees.

Why it matters: Without union by rank or size, trees can become tall, making find operations slow and degrading performance.

Quick: Does path compression change the set leaders? Commit to yes or no.

Common Belief: Path compression changes the leader of a set during find operations.

Reality: Path compression only changes parent links to point directly to the leader; it does not change the leader itself.

Why it matters: Misunderstanding this can lead to incorrect assumptions about set membership and cause bugs in algorithms relying on stable leaders.

Quick: Is Union Find suitable for handling edge deletions in dynamic graphs? Commit to yes or no.

Common Belief: Union Find can handle edge deletions efficiently in dynamic graphs.

Reality: Standard Union Find cannot handle deletions efficiently; specialized dynamic connectivity data structures are needed.

Why it matters: Using Union Find for deletions leads to incorrect results or requires rebuilding the structure, causing inefficiency.

Quick: Does Union Find store all elements of a set explicitly? Commit to yes or no.

Common Belief: Union Find keeps a list of all elements in each set.

Reality: Union Find only stores parent links and leaders; it does not explicitly store all set members.

Why it matters: Expecting explicit member lists can cause confusion and incorrect implementations when trying to enumerate set elements.

Expert Zone

1

Union Find's efficiency depends heavily on the combination of path compression and union by rank; using only one optimization yields suboptimal performance.

2

The inverse Ackermann function complexity is so slow-growing that for all practical input sizes, Union Find operations are effectively constant time.

3

Persistent Union Find implementations require careful management of versioning and can be combined with segment trees or binary indexed trees for offline queries.

When NOT to use

Union Find is not suitable when you need to handle deletions of connections dynamically or when you need to list all members of a set efficiently. In such cases, use dynamic connectivity data structures like Link-Cut Trees or Euler Tour Trees, or maintain explicit member lists with balanced trees.

Production Patterns

Union Find is widely used in Kruskal's algorithm for Minimum Spanning Trees, network connectivity checks, image processing for connected components, clustering algorithms, and social network friend group detection. It is also used in offline query processing where queries about connectivity are answered after all unions.

Connections

Graph Theory

Union Find is a fundamental tool to manage connected components in graphs.

Understanding Union Find helps grasp how graph connectivity is maintained and updated efficiently during edge additions.

Database Transactions

Persistent Union Find relates to version control and rollback mechanisms in databases.

Knowing persistent data structures like Union Find variants aids in designing systems that support undo and historical queries.

Social Networks

Union Find models friend groups and communities by grouping connected users.

Recognizing Union Find's role in social network analysis helps understand how large-scale user connections are managed efficiently.

Common Pitfalls

#1 Not using path compression causes slow find operations.

Wrong approach:

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

Correct approach:

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

Root cause:

Forgetting to update parent links during find leads to tall trees and slow queries.

#2 Union without checking leaders causes incorrect merges.

Wrong approach:

void unionSets(int a, int b) {
parent[a] = b;
}

Correct approach:

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

Root cause:

Not finding leaders before union merges elements incorrectly, breaking set structure.

#3 Ignoring union by rank leads to unbalanced trees.

Wrong approach:

void unionSets(int a, int b) {
parent[find(a)] = find(b);
}

Correct approach:

void unionSets(int a, int b) {
int rootA = find(a);
int rootB = find(b);
if (rank[rootA] < rank[rootB]) parent[rootA] = rootB;
else if (rank[rootB] < rank[rootA]) parent[rootB] = rootA;
else {
parent[rootB] = rootA;
rank[rootA]++;
}
}

Root cause:

Not balancing trees during union causes deep trees and slow find operations.

Key Takeaways

Union Find Disjoint Set efficiently manages groups of connected elements with fast union and find operations.

Path compression and union by rank are crucial optimizations that keep operations nearly constant time.

The data structure represents sets as trees with leaders, enabling quick membership checks and merges.

Union Find is foundational for many graph algorithms and real-world applications involving connectivity.

Advanced variants support undo operations and dynamic changes, extending its usefulness beyond static problems.

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