Union-Find (Disjoint Set Union / DSU)
Union-Find (Disjoint Set Union) maintains a partition of elements into disjoint sets with near-constant O(alpha(n)) find and union operations using path compression and union by rank/size.
Difficulty: Medium · Interactive Visualizer · C++ / Python / Java / JS Code
Union-Find (Disjoint Set Union / DSU)
Union-Find (also called Disjoint Set Union / DSU) tracks a collection of disjoint sets and supports two operations in $O(\alpha(n))$ amortized time (where $\alpha$ is the inverse Ackermann function, $\alpha(n) \le 4$ for every $n$ smaller than the number of atoms in the universe!):
find(x): Returns the canonical representative (root) ofx's set.unite(a, b): Merges the sets containingaandb.
Combining Path Compression (flattening parent pointers during find) with Union by Rank / Size (attaching the smaller tree under the larger root) gives near-$O(1)$ speed in ~12 lines of code!
At a Glance
| Operation | Time Complexity |
| :--- | :---: |
| find(x) | $O(\alpha(n)) \approx O(1)$ amortized |
| unite(a, b) | $O(\alpha(n)) \approx O(1)$ amortized |
| connected(a, b) | $O(\alpha(n)) \approx O(1)$ amortized |
| Auxiliary Space | $O(n)$ |
---
Practice Problems
Easy
1. Reusable DSU Template (Path Compression + Union by Size)
Implement a clean DSU tracking component count and component sizes in $O(\alpha(n))$ per op.
Approach: Maintain parent[] and sz[]; flatten paths in find(x) and merge smaller into larger in unite(a, b).
<details>
<summary>Show C++ Solution</summary>
#include <iostream>
#include <numeric>
#include <utility>
#include <vector>
struct DSU {
std::vector<int> p, sz;
int components;
explicit DSU(int n) : p(n), sz(n, 1), components(n) {
std::iota(p.begin(), p.end(), 0);
}
int find(int x) { return p[x] == x ? x : p[x] = find(p[x]); }
bool unite(int a, int b) {
a = find(a); b = find(b);
if (a == b) return false;
if (sz[a] < sz[b]) std::swap(a, b);
p[b] = a;
sz[a] += sz[b];
--components;
return true;
}
int sizeOf(int x) { return sz[find(x)]; }
};
int main() {
DSU dsu(5);
dsu.unite(0, 1); dsu.unite(1, 2); dsu.unite(3, 4);
std::cout << "Components: " << dsu.components << " | size(0)=" << dsu.sizeOf(0) << "\n";
return 0;
}
</details>
---
Intermediate
2. Redundant Connection (Find Cycle-Forming Edge, LeetCode 684)
Given an undirected graph formed by adding one extra edge to an $n$-node tree (1..n), return the edge that creates a cycle.
Approach: Process edges one by one; the first edge (u, v) where !dsu.unite(u, v) (find(u) == find(v)) is the redundant edge! Time: $O(n \alpha(n))$.
<details>
<summary>Show C++ Solution</summary>
#include <iostream>
#include <numeric>
#include <utility>
#include <vector>
std::pair<int, int> findRedundantEdge(int n, const std::vector<std::pair<int, int>>& edges) {
std::vector<int> p(n + 1);
std::iota(p.begin(), p.end(), 0);
auto find = [&](auto& self, int x) -> int { return p[x] == x ? x : p[x] = self(self, p[x]); };
for (const auto& [u, v] : edges) {
int ru = find(find, u), rv = find(find, v);
if (ru == rv) return {u, v};
p[ru] = rv;
}
return {-1, -1};
}
int main() {
auto [u, v] = findRedundantEdge(3, {{1, 2}, {1, 3}, {2, 3}});
std::cout << u << "-" << v << "\n"; // 2-3
return 0;
}
</details>
---
Related Structures & Algorithms
- Disjoint Set — companion reference with weighted/bipartite DSU variants.
- Kruskal's Algorithm — powered by Union-Find for $O(E \log E)$ MSTs.