Log inSign up
mediumGeeksforGeeksNot Started

Disjoint Set Union

Implement the Disjoint Set Union (DSU / Union-Find) data structure supporting find(u) to determine the component representative and union(u, v) to merge two disjoint sets with near O(1) amortized complexity.

Graph
Solve on GeeksforGeeks
Lesson

Problem Statement

### Problem Statement

Implement the Disjoint Set Union (DSU), also known as the Union-Find data structure, for N elements numbered 1 to N (or 0 to N - 1).

The data structure must support two primary operations: 1. find(u): Returns the representative (or root) of the set containing element u. 2. unionSets(u, v): Merges the set containing element u with the set containing element v. If they are already in the same set, do nothing.

Optimize both operations so that any sequence of M operations runs in near-linear time O(M * α(N)), where α is the Inverse Ackermann function.

---

### Examples

Example 1: ``text Operations: unionSets(1, 2) unionSets(2, 3) find(1) == find(3) -> true (same component) find(1) == find(4) -> false (4 is in a separate component)

Example 2 (Cycle Detection): ``text Edges: (1, 2), (2, 3), (3, 1) - union(1, 2): Success - union(2, 3): Success - union(3, 1): find(3) == find(1) -> Cycle detected!

---

### Constraints - 1 <= N <= 10^5 - 1 <= operations.length <= 10^5 - All element queries are within valid range [1, N].

Constraints:

  • 1 <= N <= 105
  • 1 <= operations <= 105
  • Elements are 0-indexed or 1-indexed

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Understand why naive disjoint set trees degenerate into O(N) linear chains.
  • Implement Path Compression recursively and iteratively.
  • Implement Union by Rank and Union by Size.
  • Analyze the Inverse Ackermann function α(N) amortized time bound.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Dynamic graph connectivity (merging components and answering connectivity queries).
  • Cycle detection in undirected graphs during edge-by-edge ingestion.
  • Kruskal's Minimum Spanning Tree algorithm.

Algorithmic Decision Tree:

  • If graph edges are static and only component queries are needed -> DFS/BFS in O(V + E).
  • If edges arrive dynamically in an online stream -> DSU is strictly required: O(α(N)) per edge.
  • If edges are removed/deleted -> Standard DSU cannot easily handle deletions; requires Offline DSU with Rollback.

Connected Patterns:

Accounts MergeNumber of ProvincesRedundant ConnectionKruskal's Algorithm

1. Quick-Find (Flat Component ID Array)

Intuition

Store component representative directly in an array. find(u) is O(1), but union(u, v) scans all N elements in O(N).

Algorithm

  1. Initialize id array where id[i] = i for all i.
  2. find(u): Return id[u] in O(1).
  3. unionSets(u, v):
  4. pid = id[u], qid = id[v].
  5. If pid == qid, return false.
  6. For every element i from 0 to N - 1: if id[i] == pid, update id[i] = qid.
  7. Return true.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4using namespace std;
5
6class QuickFind {
7 vector<int> id;
8public:
9 QuickFind(int n) : id(n) {
10 for (int i = 0; i < n; ++i) id[i] = i;
11 }
12
13 int find(int u) {
14 return id[u];
15 }
16
17 bool unionSets(int u, int v) {
18 int pid = id[u];
19 int qid = id[v];
20 if (pid == qid) return false;
21
22 for (int i = 0; i < id.size(); ++i) {
23 if (id[i] == pid) id[i] = qid;
24 }
25 return true;
26 }
27};
28
29int main() {
30 QuickFind dsu(5);
31 dsu.unionSets(0, 1);
32 dsu.unionSets(1, 2);
33 cout << "Connected 0 and 2: " << (dsu.find(0) == dsu.find(2) ? "true" : "false") << endl;
34 cout << "Connected 0 and 3: " << (dsu.find(0) == dsu.find(3) ? "true" : "false") << endl;
35 return 0;
36}

Time & Space Complexity

  • Time complexity: Find: O(1), Union: O(N)
  • Space complexity: O(N)

2. Quick-Union without Heuristics (Naive Parent Tree)

Intuition

Elements point to parents. union(u, v) sets parent[rootU] = rootV without rank or compression. Tree can degrade into an O(N) chain.

Algorithm

  1. Initialize parent array where parent[i] = i.
  2. find(u): Follow parent pointers while u != parent[u], set u = parent[u]. Return u.
  3. unionSets(u, v):
  4. rootU = find(u), rootV = find(v).
  5. If rootU == rootV, return false.
  6. Set parent[rootU] = rootV.
  7. Return true.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4using namespace std;
5
6class QuickUnion {
7 vector<int> parent;
8public:
9 QuickUnion(int n) : parent(n) {
10 for (int i = 0; i < n; ++i) parent[i] = i;
11 }
12
13 int find(int u) {
14 while (u != parent[u]) {
15 u = parent[u];
16 }
17 return u;
18 }
19
20 bool unionSets(int u, int v) {
21 int rootU = find(u);
22 int rootV = find(v);
23 if (rootU == rootV) return false;
24 parent[rootU] = rootV;
25 return true;
26 }
27};
28
29int main() {
30 QuickUnion dsu(5);
31 dsu.unionSets(0, 1);
32 dsu.unionSets(1, 2);
33 cout << "Connected 0 and 2: " << (dsu.find(0) == dsu.find(2) ? "true" : "false") << endl;
34 return 0;
35}

Time & Space Complexity

  • Time complexity: Find: O(N) worst case, Union: O(N) worst case
  • Space complexity: O(N)

3. Disjoint Set Union with Path Compression and Union by Rank/Size

Intuition

Combine Path Compression during find(u) with Union by Rank during unionSets(u, v) to achieve near O(1) amortized time O(α(N)).

Algorithm

  1. Initialize parent array with parent[i] = i, and rank array with rank[i] = 0 (or size array with size[i] = 1).
  2. find(u):
  3. If u == parent[u], return u.
  4. Otherwise, set parent[u] = find(parent[u]) (Path Compression).
  5. Return parent[u].
  6. unionSets(u, v):
  7. rootU = find(u), rootV = find(v).
  8. If rootU == rootV, return false (already in same component).
  9. If rank[rootU] < rank[rootV]: parent[rootU] = rootV.
  10. Else if rank[rootV] < rank[rootU]: parent[rootV] = rootU.
  11. Else: parent[rootV] = rootU, rank[rootU]++.
  12. Return true.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <numeric>
4
5using namespace std;
6
7class DSU {
8 vector<int> parent;
9 vector<int> rank;
10 vector<int> size;
11 int numComponents;
12
13public:
14 DSU(int n) : parent(n), rank(n, 0), size(n, 1), numComponents(n) {
15 iota(parent.begin(), parent.end(), 0);
16 }
17
18 int find(int u) {
19 if (u == parent[u]) return u;
20 return parent[u] = find(parent[u]); // Path compression
21 }
22
23 bool unionSets(int u, int v) {
24 int rootU = find(u);
25 int rootV = find(v);
26 if (rootU == rootV) return false;
27
28 // Union by rank
29 if (rank[rootU] < rank[rootV]) {
30 parent[rootU] = rootV;
31 size[rootV] += size[rootU];
32 } else if (rank[rootV] < rank[rootU]) {
33 parent[rootV] = rootU;
34 size[rootU] += size[rootV];
35 } else {
36 parent[rootV] = rootU;
37 size[rootU] += size[rootV];
38 rank[rootU]++;
39 }
40 numComponents--;
41 return true;
42 }
43
44 bool isConnected(int u, int v) {
45 return find(u) == find(v);
46 }
47
48 int getComponentSize(int u) {
49 return size[find(u)];
50 }
51
52 int count() const {
53 return numComponents;
54 }
55};
56
57int main() {
58 DSU dsu(5);
59 dsu.unionSets(0, 1);
60 dsu.unionSets(2, 3);
61 dsu.unionSets(1, 3);
62
63 cout << "Connected 0 and 3: " << (dsu.isConnected(0, 3) ? "true" : "false") << endl;
64 cout << "Connected 0 and 4: " << (dsu.isConnected(0, 4) ? "true" : "false") << endl;
65 cout << "Component size of 0: " << dsu.getComponentSize(0) << endl;
66 cout << "Total components remaining: " << dsu.count() << endl;
67 return 0;
68}

Time & Space Complexity

  • Time complexity: Amortized O(α(N)) per operation
  • Space complexity: O(N)

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Quick-Find (Array of Component IDs)Find: O(1), Union: O(N)O(N)Every element stores its component ID directly in an array. Union scans all N elements to rename IDs.Scanning entire array on every union.
2.Quick-Union without Heuristics (Naive Tree)Find: O(N) worst case, Union: O(N) worst caseO(N)Parent pointer tree. Union points one root to another without balancing.Tree height can grow to O(N).
3.Optimal DSU (Path Compression + Union by Rank/Size)OptimalAmortized O(α(N)) ≈ O(1) per operationO(N)Path compression flattens nodes to root on find(). Union by rank balances tree depth on union().None. Mathematically optimal for online disjoint set maintenance.

Common Pitfalls & Crucial Edge Cases

Missing path compression assignment

Writing return find(parent[u]) instead of parent[u] = find(parent[u]) eliminates the compression optimization.

Unifying nodes directly instead of their roots

Calling parent[u] = v instead of parent[rootU] = rootV corrupts component structure.

Incrementing rank incorrectly

Rank should only increase by 1 when merging two components of EQUAL rank.

Crucial Edge Cases to Validate:

  • Union of elements already in the same set — find(u) == find(v); no-op that returns false without increasing rank.
  • Single-element sets — Initially every node is its own parent with rank 0 (or size 1).
  • Large N with linear chain input — Path compression immediately collapses the chain on first lookup.
  • Query on isolated node — find(u) returns u.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. State that DSU achieves O(α(N)) amortized time, where α is the Inverse Ackermann function.
  2. Explain both Union by Rank (depth heuristic) and Union by Size (node count heuristic), noting that Union by Size also makes it trivial to query component sizes.
  3. Mention standard applications: Kruskal's MST, Dynamic Connectivity, and Bipartite Graph testing.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.How does Path Compression optimize the find(u) operation?

2.What is the primary purpose of Union by Rank?

Back to DSA Sheet