DSA Graphs
Disjoint Set Union
You keep merging friend circles as edges arrive online. After each friendship, the question is the same: are A and B already in one circle, or should two circles become one?
DSU (Union-Find) maintains a partition into with near-constant and , using and .
Algorithm journey
n singletons
Each element parents itself; component count = n.
Climb to root; compress the path.
Link roots by rank/size if they differ.
Same component?
Compare representatives.
What actually happens
Naive idea: rebuild connected components with BFS after every new edge. Correct, and Θ(V+E) per update. At 10⁵ unions that becomes brutal.
Better idea: store a forest of trees, one tree per component. Find follows parents to a root; union links roots. Path compression and union by rank/size keep trees flat.
The improved design still fails at undoing merges (path compression destroys history), at treating directed reachability as undirected equivalence, and if non-root size/rank fields are trusted after compression.
Invariant
The parent forest partitions the n elements into disjoint components: every node has one parent; roots parent themselves; find(x) returns the unique root of x's component. A successful union merges exactly two roots and decreases the component count by one.
How to choose DSU
1. Edges only added? DSU shines for incremental connectivity, Kruskal, and offline “activate edges by threshold” queries.
2. Need deletions or rollbacks? Ordinary path compression will not help; use rollback DSU (union-by-size, no compression) or a heavier dynamic structure.
3. Full graph already known, one-shot components? A single BFS/DFS pass is enough; DSU is optional sugar.
Quantitative check
With path compression and union by rank/size, m operations on n elements cost O(m α(n)) amortized. α(n) < 5 for any practical n: at n = 10⁶ and m = 10⁶ unions/finds, think “almost linear,” not “literally one CPU instruction per call.”
Core operations
Find
Determines which subset a particular element is in. Compare two finds to test whether elements share a component.
Efficiency: path compression
Union
Joins two subsets into a single subset when their roots differ.
Efficiency: union by rank or size
Interactive parent-forest trace
Union–find invariant lab
Representatives, sizes, and path compression
0
parent 0
size 1
1
parent 1
size 1
2
parent 2
size 1
3
parent 3
size 1
4
parent 4
size 1
{0}{1}{2}{3}{4}Step 1 of 6
Start
Every item is its own representative.
Invariant: roots parent themselves; only roots own valid sizes; two items are connected iff their representatives match.
Optimized implementation
Path compression plus union by size. Rank is an equally valid linking heuristic; keep metadata only on roots.
Python
class DSU:
def __init__(self, n):
if n < 0:
raise ValueError("n must be non-negative")
self.parent = list(range(n))
self.size = [1] * n
self.components = n
def find(self, i):
if not 0 <= i < len(self.parent):
raise IndexError(i)
# Path Compression
if self.parent[i] == i:
return i
self.parent[i] = self.find(self.parent[i])
return self.parent[i]
def union(self, i, j):
root_i = self.find(i)
root_j = self.find(j)
if root_i != root_j:
# Union by size: attach the smaller root.
if self.size[root_i] < self.size[root_j]:
root_i, root_j = root_j, root_i
self.parent[root_j] = root_i
self.size[root_i] += self.size[root_j]
self.components -= 1
return True
return False
dsu = DSU(4)
assert dsu.union(0, 1) and dsu.union(2, 3) and dsu.union(1, 3)
assert dsu.find(0) == dsu.find(2) and dsu.components == 1Java
class DSU {
int[] parent;
int[] size;
int components;
public DSU(int n) {
if (n < 0) throw new IllegalArgumentException("n must be non-negative");
parent = new int[n];
size = new int[n];
components = n;
for (int i = 0; i < n; i++) { parent[i] = i; size[i] = 1; }
}
public int find(int i) {
if (i < 0 || i >= parent.length) throw new IndexOutOfBoundsException(i);
if (parent[i] == i) return i;
// Path Compression
return parent[i] = find(parent[i]);
}
public boolean union(int i, int j) {
int rootI = find(i);
int rootJ = find(j);
if (rootI != rootJ) {
if (size[rootI] < size[rootJ]) {
int temp = rootI; rootI = rootJ; rootJ = temp;
}
parent[rootJ] = rootI;
size[rootI] += size[rootJ];
components--;
return true;
}
return false;
}
public static void main(String[] args) {
DSU dsu = new DSU(4);
if (!dsu.union(0, 1) || !dsu.union(2, 3) || !dsu.union(1, 3)) throw new AssertionError();
if (dsu.find(0) != dsu.find(2) || dsu.components != 1) throw new AssertionError();
}
}Invariant and amortized analysis
Forest shape
Every node has one parent; roots parent themselves. find(x) returns the unique root.
Root metadata
Only roots own authoritative component size. A successful union reduces component count by one.
Equivalence relation
connected(a,b) iff find(a)=find(b); reflexive, symmetric, and transitive connectivity is represented by one partition.
Union-by-size alone keeps height O(log n). Path compression alone flattens paths across repeated finds. Together, any sequence of m operations costs O(m α(n)) amortized. α is the inverse Ackermann function: below five for practical inputs, but this is an amortized theorem, not literal worst-case O(1) per call.
Failure timeline: linking without heuristics
- Always attach root A under root B regardless of size: a long chain of unions can build height Θ(n).
- Each find walks the chain: a burst of finds costs Θ(n) each before compression helps.
- Repair: union by size/rank bounds height; path compression then flattens hot paths for later queries.
Where DSU fits, and where it does not
| Problem | Offline/online pattern | DSU role |
|---|---|---|
| Undirected cycle / components | Edges only added | Failed union detects an existing path |
| Kruskal MST | Edges sorted by weight | Reject cycle edges between equal representatives |
| Accounts/islands grouping | Equivalence links accumulated | Merge identities and aggregate by final root |
| Offline threshold queries | Sort edges and queries together | Answer connectivity after activating eligible edges |
Production checklist
- Map arbitrary IDs to dense indices or use a documented hash-backed variant.
- Validate indices; expose component count and size only through representatives.
- Use iterative find/path halving if recursion depth is a concern.
- Do not confuse directed reachability with undirected equivalence.
- Test repeated/self union, chains, stars, isolated nodes, and duplicate edges.
- Assert roots self-parent and root sizes sum to n.
- Cross-check random operations against a graph BFS oracle.
- Concurrency needs synchronization; naive parallel parent writes race.
Complexity
| Operation | Amortized time | Notes |
|---|---|---|
| Find | O(α(n)) | With path compression + union by rank/size |
| Union | O(α(n)) | Two finds plus a constant-time link |
Exercises
- Start with n = 8 singletons. Union (0,1), (2,3), (1,3), (4,5) with union by size. Sketch the forest and component count after each step. Which unions return false if repeated?
- Why is a failed union a cycle certificate in an undirected edge-addition stream? Give a three-edge counterexample timeline.
- You need to undo the last 100 unions. Why is path compression a problem, and what linking policy remains safe for rollback DSU?
Primary sources
- Cormen et al., Introduction to Algorithms (CLRS): disjoint-set forests; path compression; union by rank; α(n).
- Tarjan, R. E.: Efficiency of a good but not linear set union algorithm (inverse Ackermann bound).
- Galil & Italiano / textbook Kruskal sections: DSU as the connectivity oracle for MST.
Takeaway
DSU maintains an equivalence partition: components are “same root” sets. Path compression plus union by rank/size make incremental connectivity practically O(1) amortized per op, until you need deletions.