Disjoint Set Union (DSU) with path compression
Scenario
You have 100,000 computers. Every second, two computers are connected with a cable. You must constantly answer queries: 'Is computer A currently connected to computer B through any series of cables?'
Running BFS/DFS on the graph for every query takes O(V+E) time, which will TLE instantly. How do you track dynamic connectivity in near O(1) time?
Why it exists
DSU is a foundational data structure in graph theory. It provides an elegantly simple, lightning-fast mechanism to track connected components and detect cycles as edges are added to a graph. It is the primary engine behind Kruskal's Algorithm for Minimum Spanning Trees and is universally used in network connectivity problems. In real-world software engineering, DSU is essential for connected component labeling in image processing, network cluster identification, and compiling linker dependencies.
Mental model
Imagine a forest of trees. Every connected component is a tree, and the 'root' of the tree is the component's leader. To check if two computers are connected, just check if they have the same leader. When connecting two components, simply make the leader of one tree point to the leader of the other.
Disjoint Set Union (DSU), also known as Union-Find, is a data structure that tracks a set of elements partitioned into a number of disjoint (non-overlapping) subsets. It supports two operations: `find` (determine which subset an element is in) and `union` (merge two subsets). With path compression, these operations run in inverse Ackermann time, which is practically `O(1)`.
Explanation
**1. Initialization:**
We use an array `parent[]`. Initially, every node is disconnected, meaning every node is its own leader: `parent[i] = i`.
**2. The Find Operation & Path Compression:**
To find the leader of node `i`, we follow the `parent` pointers until we hit a node that points to itself (`parent[root] == root`).
*Path Compression:* While searching for the root, we recursively update every visited node to point *directly* to the root. This flattens the tree. The next time we call `find` on those nodes, it takes exactly O(1) time!
**3. The Union Operation:**
To connect node `A` and node `B`, we find their leaders: `rootA = find(A)` and `rootB = find(B)`. If they are different, we merge them by pointing one root to the other: `parent[rootA] = rootB`.
*Union by Size/Rank:* To keep the tree perfectly balanced before Path Compression kicks in, we should always attach the smaller tree to the root of the larger tree. This guarantees the tree depth never exceeds O(log N).
When you combine Path Compression and Union by Rank, the time complexity becomes `O(\alpha(N))`, where `\alpha` is the inverse Ackermann function. For any conceivable number in the universe, `\alpha(N) < 5`. It is practically O(1).
**4. Tracking Metadata (Aggregates):**
The root of a component can store arbitrary metadata for the entire set (like maximum element, sum, or size). When calling `unite(A, B)`, you simply update the new root: `max_val[rootA] = max(max_val[rootA], max_val[rootB])`. This maintains O(1) queries for component-wide properties.
Code examples
DSU (Union-Find) Implementation
vector<int> parent;
vector<int> sz; // size of the component
void init(int n) {
parent.resize(n);
sz.resize(n, 1);
for (int i = 0; i < n; i++) parent[i] = i;
}
int find(int i) {
// Path compression: recursively point to the ultimate root
if (parent[i] == i) return i;
return parent[i] = find(parent[i]);
}
void unite(int i, int j) {
int rootI = find(i);
int rootJ = find(j);
if (rootI != rootJ) {
// Union by size: attach smaller tree to larger tree
if (sz[rootI] < sz[rootJ]) swap(rootI, rootJ);
parent[rootJ] = rootI;
sz[rootI] += sz[rootJ];
}
}This 20-line struct is the backbone of Kruskal's Minimum Spanning Tree algorithm and is a mandatory tool for any graph connectivity problem.
Key points
- The ultimate cycle detector: If you `union` two nodes that already share the same root, you have just detected a cycle.
- Almost O(1): The time complexity is the inverse Ackermann function, which is effectively constant time.
Common mistakes
- Forgetting Path Compression: If you write `return find(parent[i]);` instead of `return parent[i] = find(parent[i]);`, the tree never flattens. In a worst-case scenario (like connecting 1-2, then 2-3, then 3-4...), the tree degrades into a linked list, and the `find` operation drops from O(1) to O(N), causing a Time Limit Exceeded error.
Recall questions
- What two heuristics/optimizations are required to achieve the O(alpha(N)) time complexity in a DSU?
- In a DSU, how do you determine if two elements `A` and `B` belong to the same connected component?
- What is the purpose of 'Union by Size'?
Questions & answers
A developer is writing Kruskal's Algorithm to find a Minimum Spanning Tree. To check if adding an edge creates a cycle, they run a Depth First Search (DFS) on their graph. The algorithm fails the time constraints. What should they use instead?
They should use a Disjoint Set Union (DSU). For each edge `(u, v)`, if `find(u) == find(v)`, a cycle is detected in O(1) time. Using DFS takes O(V+E) time per edge, which is drastically slower.
Approach: Identify DSU as the optimal data structure for dynamic cycle detection.
A team tries to use a DSU to answer queries like: 'What is the maximum element in the connected component containing node X?'. Can DSU support this?
Yes. DSU can be easily augmented. Alongside the `parent` and `size` arrays, you maintain a `max_val` array. Whenever `unite(A, B)` is called, you simply update `max_val[rootA] = max(max_val[rootA], max_val[rootB])`. This maintains O(1) queries for component-wide maximums.
Approach: Recognize that DSU roots can store arbitrary aggregate metadata for the entire component.