Union-Find in Depth
Why this exists
Many problems reduce to one question asked over and over while the data changes: are these two things in the same group? Two computers on a network after a cable is plugged in. Two pixels of the same blob in a scanned image. Two type variables a compiler has been told must be equal. Two accounts that share an email address. Each new fact merges two groups; groups never split. A graph search answers the question once in , but if facts and questions interleave — merges and queries — re-running BFS for every question is steps.
The disjoint-set union (DSU), or union-find, maintains a partition of elements under two operations: find(x) returns a canonical representative of the set containing , and union(a, b) merges the sets containing and . "Same group?" is find(a) == find(b). With two small tricks — attach the smaller tree under the larger, and flatten paths as you walk them — a sequence of operations on elements costs , where is the inverse of the Ackermann function. grows so slowly that it is at most 4 for any input that fits in the observable universe. It is the closest thing to a free lunch in data structures: about fifteen lines of code with a bound that took a decade of research to pin down.
The history is short and instructive. Bernard Galler and Michael Fischer described the forest representation in 1964 ("An improved equivalence algorithm", Communications of the ACM 7(5)), motivated by Fortran's EQUIVALENCE statements, which tell the compiler that several variables share storage. Hopcroft and Ullman proved an amortized bound for union by rank with path compression in 1973. Robert Tarjan proved the tight bound in 1975 ("Efficiency of a Good But Not Linear Set Union Algorithm", JACM 22(2)), and Tarjan and van Leeuwen extended it to path halving, path splitting and many linking rules in 1984 ("Worst-case analysis of set union algorithms", JACM 31(2)). Fredman and Saks showed in 1989 that no data structure in the cell-probe model can beat amortized per operation, so the bound is optimal, not just an artifact of the analysis.
The Graphs overview and the DSU section of Advanced Data Structures give the standard implementation. This lesson starts from the naive versions and their worst cases, proves why each improvement works, states the inverse-Ackermann bound precisely, proves the simpler bound, and then covers the variants that show up in contests and production: rollback, weighted (potential) DSU, parity DSU for bipartiteness, and offline dynamic connectivity. The next lesson, Minimum Spanning Trees, is the most famous client.
Pattern triggers
| If the problem says or has… | Think of… |
|---|---|
| "are and connected?" interleaved with "connect and " | Plain DSU |
| Count connected components / groups / provinces / islands as edges arrive | DSU with a count field |
| "size of the largest group" after each merge | DSU with union by size, track the max |
| Process edges in sorted order, join while something holds | Kruskal-style DSU (MST, bottleneck paths, offline threshold queries) |
| "the first edge that closes a cycle", "redundant connection" | DSU: an edge whose endpoints already share a root |
Equalities a == b then checks a != b | DSU on variables, then verify each inequality |
| "a / b = 2.0, b / c = 3.0, what is a / c?" | Weighted DSU (multiplicative potential) |
| "x is 5 heavier than y", relative offsets, consistency of differences | Weighted DSU (additive potential) |
| "same team / opposite team", "is the graph still bipartite after each edge?" | Parity DSU |
| Merge accounts / records / users that share any key | DSU over records keyed by the shared attribute |
| Edges are added and removed, all queries known in advance | Rollback DSU + segment tree over time |
| "undo the last k merges", divide and conquer over queries | Rollback DSU (union by size, no path compression) |
| Grid cells switch on one by one; count islands each time | DSU over cells (Number of Islands II, percolation) |
| Queries about thresholds: "paths using only edges ≤ limit" | Sort queries and edges, sweep with a DSU |
| Groups split (an edge is deleted) online | Not plain DSU — needs link-cut trees or dynamic connectivity structures |
The meta-trigger: an equivalence relation that only ever gets coarser. Reflexive, symmetric, transitive, and merges only. If groups must split online, union-find alone cannot do it.
Intuition & first principles
Think of each set as a club with a president. Every member knows someone in the club closer to the president — their parent — and the president is their own parent. To find out which club you are in, follow parent links until you reach someone who points to themselves; that is the root, and it names the set. To merge two clubs, one president agrees to report to the other. That is the whole data structure: an array parent[] that encodes a forest of rooted trees, one tree per set.
The precise statement: we maintain a partition of . Each is stored as a rooted tree whose nodes are exactly the elements of ; is 's parent and for the root . find(x) returns the root of 's tree; union(a, b) makes one root a child of the other. Correctness is obvious — two elements are in the same set exactly when they are in the same tree, exactly when their roots are equal. The entire subject is about cost: how deep can the trees get, and how much work do we spend walking them?
Three observations drive everything that follows:
- The cost of
findis the depth of the node. Union is two finds plus . So we want shallow trees. - We choose which root goes under which. Putting a big tree under a small one makes every node in the big tree one level deeper; the other way round, fewer nodes get deeper. This is union by size (or by rank).
- After walking a path to the root, we know the root for every node on it. We can re-point all of them directly to the root for free (a constant factor on a walk we already paid for). This is path compression.
Either trick alone gives amortized. Together they give . Neither ever changes which sets exist — only the shape of the trees inside them, which is invisible to the user of the API.
Two levels to keep separate
The abstract object is a partition of elements into sets. The concrete object is a forest of parent pointers. Many different forests represent the same partition, and every optimization in this lesson is a way of choosing a cheaper forest for the same partition.
Mechanics
The naive versions and their worst cases
Quick-find stores the set label directly: id[x] is the name of 's set. find is one array read, . union(a, b) must relabel every element of one set, which means scanning the whole array: . A sequence of unions that joins everything costs — about array reads for .
Quick-union is the forest without any balancing: union(a, b) sets parent[find(a)] = find(b). Union is now cheap if finds are cheap, but nothing stops the trees from degenerating into a path. The sequence union(0, 1), union(1, 2), …, union(n-2, n-1) makes 0 → 1 → 2 → … → n-1: each union finds two roots in (the left argument is always a root at that moment), but find(0) now walks links. Repeating find(0) times costs hops — measured below as 16,773,120 hops for .
flowchart LR
subgraph QU["quick-union after union(i, i+1) for all i"]
direction LR
q0((0)) --> q1((1)) --> q2((2)) --> q3((3)) --> q4((4)) --> q5((5))
end
subgraph US["union by size on the same calls"]
direction TB
u1((1)) --> u0((0))
u2((2)) --> u0
u3((3)) --> u0
u4((4)) --> u0
u5((5)) --> u0
end
Arrows point from child to parent. On the left, find(0) walks 5 links; on the right every node is one link from the root, because union by size always hangs the singleton under the big tree.
# The two naive structures, instrumented to count work.
class QuickFind:
def __init__(self, n: int) -> None:
self.id = list(range(n))
self.reads = 0
def find(self, x: int) -> int:
self.reads += 1
return self.id[x]
def union(self, a: int, b: int) -> None:
ia, ib = self.find(a), self.find(b)
if ia == ib:
return
for i in range(len(self.id)): # relabel every member of a's set
self.reads += 1
if self.id[i] == ia:
self.id[i] = ib
class QuickUnion:
def __init__(self, n: int) -> None:
self.parent = list(range(n))
self.hops = 0
def find(self, x: int) -> int:
while self.parent[x] != x:
x = self.parent[x]
self.hops += 1
return x
def union(self, a: int, b: int) -> None:
ra, rb = self.find(a), self.find(b)
if ra != rb:
self.parent[ra] = rb # no balancing at all
def main() -> None:
n = 4096
qf = QuickFind(n)
for i in range(n - 1):
qf.union(i, i + 1)
assert len(set(qf.id)) == 1
# each union: 2 reads for the two finds + n reads for the scan
assert qf.reads == (n - 1) * (n + 2)
qu = QuickUnion(n)
for i in range(n - 1):
qu.union(i, i + 1) # builds the chain 0 -> 1 -> ... -> n-1
assert qu.hops == 0 # every union met two roots
for _ in range(n):
assert qu.find(0) == n - 1
assert qu.hops == n * (n - 1) == 16_773_120
print("quick-find reads:", qf.reads, " quick-union hops:", qu.hops)
main()
public class NaiveUnionFind {
static final class QuickFind {
final int[] id;
long reads = 0;
QuickFind(int n) { id = new int[n]; for (int i = 0; i < n; i++) id[i] = i; }
int find(int x) { reads++; return id[x]; }
void union(int a, int b) {
int ia = find(a), ib = find(b);
if (ia == ib) return;
for (int i = 0; i < id.length; i++) { // relabel every member of a's set
reads++;
if (id[i] == ia) id[i] = ib;
}
}
}
static final class QuickUnion {
final int[] parent;
long hops = 0;
QuickUnion(int n) { parent = new int[n]; for (int i = 0; i < n; i++) parent[i] = i; }
int find(int x) {
while (parent[x] != x) { x = parent[x]; hops++; }
return x;
}
void union(int a, int b) {
int ra = find(a), rb = find(b);
if (ra != rb) parent[ra] = rb; // no balancing at all
}
}
public static void main(String[] args) {
int n = 4096;
QuickFind qf = new QuickFind(n);
for (int i = 0; i < n - 1; i++) qf.union(i, i + 1);
for (int i = 0; i < n; i++) if (qf.id[i] != qf.id[0]) throw new AssertionError("not one set");
if (qf.reads != (long) (n - 1) * (n + 2)) throw new AssertionError("quick-find reads " + qf.reads);
QuickUnion qu = new QuickUnion(n);
for (int i = 0; i < n - 1; i++) qu.union(i, i + 1);
if (qu.hops != 0) throw new AssertionError("unions should meet roots");
for (int k = 0; k < n; k++) if (qu.find(0) != n - 1) throw new AssertionError("wrong root");
if (qu.hops != (long) n * (n - 1) || qu.hops != 16_773_120L) throw new AssertionError("hops " + qu.hops);
System.out.println("quick-find reads: " + qf.reads + " quick-union hops: " + qu.hops);
}
}
#include <cassert>
#include <cstdint>
#include <iostream>
#include <numeric>
#include <vector>
struct QuickFind {
std::vector<int> id;
std::int64_t reads = 0;
explicit QuickFind(int n) : id(n) { std::iota(id.begin(), id.end(), 0); }
int find(int x) { ++reads; return id[x]; }
void unite(int a, int b) {
int ia = find(a), ib = find(b);
if (ia == ib) return;
for (int& v : id) { // relabel every member of a's set
++reads;
if (v == ia) v = ib;
}
}
};
struct QuickUnion {
std::vector<int> parent;
std::int64_t hops = 0;
explicit QuickUnion(int n) : parent(n) { std::iota(parent.begin(), parent.end(), 0); }
int find(int x) {
while (parent[x] != x) { x = parent[x]; ++hops; }
return x;
}
void unite(int a, int b) {
int ra = find(a), rb = find(b);
if (ra != rb) parent[ra] = rb; // no balancing at all
}
};
int main() {
const int n = 4096;
QuickFind qf(n);
for (int i = 0; i < n - 1; ++i) qf.unite(i, i + 1);
for (int v : qf.id) assert(v == qf.id[0]);
assert(qf.reads == static_cast<std::int64_t>(n - 1) * (n + 2));
QuickUnion qu(n);
for (int i = 0; i < n - 1; ++i) qu.unite(i, i + 1);
assert(qu.hops == 0);
for (int k = 0; k < n; ++k) assert(qu.find(0) == n - 1);
assert(qu.hops == static_cast<std::int64_t>(n) * (n - 1) && qu.hops == 16773120);
std::cout << "quick-find reads: " << qf.reads << " quick-union hops: " << qu.hops << "\n";
}
class QuickFind {
id: number[];
reads = 0;
constructor(n: number) {
this.id = Array.from({ length: n }, (_, i) => i);
}
find(x: number): number {
this.reads++;
return this.id[x];
}
union(a: number, b: number): void {
const ia = this.find(a), ib = this.find(b);
if (ia === ib) return;
for (let i = 0; i < this.id.length; i++) { // relabel every member of a's set
this.reads++;
if (this.id[i] === ia) this.id[i] = ib;
}
}
}
class QuickUnion {
parent: number[];
hops = 0;
constructor(n: number) {
this.parent = Array.from({ length: n }, (_, i) => i);
}
find(x: number): number {
while (this.parent[x] !== x) {
x = this.parent[x];
this.hops++;
}
return x;
}
union(a: number, b: number): void {
const ra = this.find(a), rb = this.find(b);
if (ra !== rb) this.parent[ra] = rb; // no balancing at all
}
}
function assert(cond: boolean, msg: string): void {
if (!cond) throw new Error(msg);
}
const n = 4096;
const qf = new QuickFind(n);
for (let i = 0; i < n - 1; i++) qf.union(i, i + 1);
assert(new Set(qf.id).size === 1, "not one set");
assert(qf.reads === (n - 1) * (n + 2), `quick-find reads ${qf.reads}`);
const qu = new QuickUnion(n);
for (let i = 0; i < n - 1; i++) qu.union(i, i + 1);
assert(qu.hops === 0, "unions should meet roots");
for (let k = 0; k < n; k++) assert(qu.find(0) === n - 1, "wrong root");
assert(qu.hops === n * (n - 1) && qu.hops === 16773120, `hops ${qu.hops}`);
console.log(`quick-find reads: ${qf.reads} quick-union hops: ${qu.hops}`);
Union by size and union by rank
The fix for quick-union is to choose the direction of each link. Two classic rules:
- Union by size: keep
size[r]= number of nodes in the tree rooted at . Attach the root of the smaller tree under the root of the larger; add the sizes. - Union by rank: keep
rank[r], an upper bound on the height of 's tree. Attach the lower-rank root under the higher-rank root; if the ranks are equal, pick either and increment the new root's rank.
Without path compression, rank is exactly the height. With path compression, heights shrink but ranks are never decreased, so rank becomes only an upper bound — which is all the analysis needs. Both rules give the same asymptotic bounds; size has the practical bonus that it answers "how big is this group?" for free, which many problems ask for. This lesson's canonical code uses size.
flowchart TD
S["union(a, b)"] --> F["ra = find(a), rb = find(b)"]
F --> Q{"ra == rb?"}
Q -->|"yes"| R0["already in one set: return false"]
Q -->|"no"| C{"size[ra] < size[rb]?"}
C -->|"yes"| SW["swap ra and rb"]
C -->|"no"| L["parent[rb] = ra"]
SW --> L
L --> U["size[ra] += size[rb]<br/>count -= 1<br/>return true"]
Claim (height bound). With union by size and no path compression, every tree with height has at least nodes. Hence the height of any tree is at most , and find costs in the worst case — not amortized, every single call.
Proof. Follow one element . Its depth increases only when its root is attached under another root , and then by exactly 1. Union by size attaches under only when , so the tree containing goes from size to at least . Starting from size 1, after depth increases lives in a tree of at least nodes. Trees have at most nodes, so , .
The same argument works for rank: by induction, a root of rank has at least nodes in its tree (a root reaches rank only by absorbing another root of rank , combining two trees of at least nodes each). So rank, and height, are at most .
The bound is tight. Merge singletons in pairs, then pairs of pairs, and so on — always two equal-size trees. The result is a binomial tree of height : for , height 12, and the measured sum of all depths is . So union by size alone gives worst-case finds, which is already enough for operations in any language.
Path compression
During find(x) we walk . Afterwards we know the root of every , so we set for all of them. The walk costs ; the re-pointing costs another writes. Future finds on any of these nodes, or any node in their subtrees, become shorter.
The two standard implementations:
- Recursive:
parent[x] = find(parent[x]); return parent[x]. Short, but recursion depth equals path length, which can be if path compression is used without union by size — and Python's default recursion limit is 1000. Avoid in Python and Java unless you also balance. - Two-pass iterative: first walk up to find the root, then walk again re-pointing each node. No recursion, same result. This is what the canonical code below uses.
flowchart LR
subgraph B["before find(6)"]
direction BT
b6((6)) --> b4((4)) --> b3((3)) --> b2((2)) --> b1((1)) --> b0((0))
b5((5)) --> b2
b7((7)) --> b0
end
subgraph A["after find(6)"]
direction BT
a6((6)) --> a0((0))
a4((4)) --> a0
a3((3)) --> a0
a2((2)) --> a0
a1((1)) --> a0
a5((5)) --> a2
a7((7)) --> a0
end
B ==>|"compress the path 6, 4, 3, 2, 1"| A
Notice what does not happen: element 5 is not on the path, so its parent pointer is untouched. It still points to 2 — but 2 now sits directly under the root, so 5 rose from depth 3 to depth 2 without being touched. Compression helps whole subtrees hanging off the path.
Path halving and path splitting
Two one-pass alternatives avoid the second walk:
- Path splitting: every node on the path is re-pointed to its grandparent:
next = parent[x]; parent[x] = parent[next]; x = next. - Path halving: every other node is re-pointed to its grandparent, and we jump to that grandparent:
parent[x] = parent[parent[x]]; x = parent[x]. It halves the path length in one pass.
Both compress less per call than full compression, but Tarjan and van Leeuwen (1984) proved that with union by rank or size they achieve the same bound. In practice path halving is often the fastest: one loop, no stack, one write per two hops, and good cache behaviour. On the random workload measured in the ladder section below it did slightly fewer total hops than full compression (54,648 vs 57,211 for and random operations) — a measurement on one workload, not a general theorem.
Hand trace: union by size + path compression
Eight elements, union by size, two-pass path compression. "Re-pointed" lists nodes whose parent actually changed during a find. Values computed by a script.
| Step | Operation | Roots found | Re-pointed | Action | parent[0..7] | Sets | Max depth |
|---|---|---|---|---|---|---|---|
| 0 | — | — | — | — | 0 1 2 3 4 5 6 7 | 8 | 0 |
| 1 | union(0, 1) | 0, 1 | — | parent[1] = 0, size[0] = 2 | 0 0 2 3 4 5 6 7 | 7 | 1 |
| 2 | union(2, 3) | 2, 3 | — | parent[3] = 2, size[2] = 2 | 0 0 2 2 4 5 6 7 | 6 | 1 |
| 3 | union(4, 5) | 4, 5 | — | parent[5] = 4, size[4] = 2 | 0 0 2 2 4 4 6 7 | 5 | 1 |
| 4 | union(6, 7) | 6, 7 | — | parent[7] = 6, size[6] = 2 | 0 0 2 2 4 4 6 6 | 4 | 1 |
| 5 | union(1, 3) | 0, 2 | — | parent[2] = 0, size[0] = 4 | 0 0 0 2 4 4 6 6 | 3 | 2 |
| 6 | union(5, 7) | 4, 6 | — | parent[6] = 4, size[4] = 4 | 0 0 0 2 4 4 4 6 | 2 | 2 |
| 7 | union(3, 7) | 0, 4 | 3, 7 | parent[4] = 0, size[0] = 8 | 0 0 0 0 0 4 4 4 | 1 | 2 |
| 8 | find(7) | 0 | 7 | — | 0 0 0 0 0 4 4 0 | 1 | 2 |
| 9 | union(5, 2) | 0, 0 | 5 | same set, return false | 0 0 0 0 0 0 4 0 | 1 | 2 |
| 10 | find(6) | 0 | 6 | — | 0 0 0 0 0 0 0 0 | 1 | 1 |
Things to notice. In step 5 the sizes tie (2 and 2), so the first root wins. In step 7 the two finds compress 3 (from 2 to 0) and 7 (from 6 to 4) before the link; 7 lands under 4, not under 0, because 4 was its root at that moment. Step 9 is a union that does nothing to the partition but still flattens 5. After ten operations every node is one hop from the root, even though the tree reached depth 2.
The ladder: brute force → better → optimal
Rung 0: search on demand
Keep an adjacency list; answer each connected(a, b) with a BFS or DFS (BFS in Depth). Union is (append an edge), query is . Fine when queries are rare; hopeless when they interleave with updates at scale. If all edges arrive before all queries, one labelling pass answers every query in — the offline special case.
Rung 1: quick-find
find is , union is . Total for merges. The measured cost for : array reads to join everything. It improves on search because queries are instant, but every merge pays for the whole array.
Rung 2: quick-union
Union is two finds plus one write; find is , and depth can be . Worst case per operation, total. It improves on quick-find on typical inputs (random unions keep trees fairly shallow) but not in the worst case: hops on the chain.
Rung 3: union by size (or rank)
Worst-case height , so every operation is — a guarantee, not an average. On the chain workload it is perfect (height 1); on the adversarial binomial workload it hits height 12 for . This is the version to use when you need undo (see rollback below), because it changes only one pointer per union.
Rung 4: union by size + path compression (or halving)
Amortized per operation. In the measurements every combination with compression ended at height 1 on these workloads, and random workloads did about half the hops of union by size alone.
Measured on (total pointer hops during finds, counted by a throwaway script):
| Workload | quick-union | by size only | compression only | size + compression | size + halving |
|---|---|---|---|---|---|
chain: union(i, i+1) then find(0) | 16,773,120 | 8,189 | 8,190 | 8,189 | 8,189 |
| binomial: pairwise merges, then find every node | — | 24,576 (height 12) | — | 8,178 | — |
| random unions/finds (seed 1) | 24,737,786 | 106,658 | 109,023 | 57,211 | 54,648 |
| Rung | union | find | Total for ops | Extra memory | Undo-friendly |
|---|---|---|---|---|---|
| Search on demand | adjacency list | yes | |||
| Quick-find | 1 array | yes | |||
| Quick-union | 1 array | yes | |||
| By size / rank | worst | 2 arrays | yes | ||
| Compression only | amortized | same | worst | 1 array | no |
| By size + compression | amortized | same | 2 arrays | no |
The "compression only" row is Tarjan and van Leeuwen's bound for path compression with arbitrary linking: for , which is amortized when and approaches constant as grows. Good, but you lose the worst-case guarantee and the analysis is harder; there is no reason not to add union by size.
Correctness
The partition is always right
The invariant: for every , following parent pointers from terminates at a root, and two elements share a root if and only if they are in the same set of the abstract partition.
- Initially every element is its own root and its own set. True.
union(a, b)with roots sets . Every element that reached now reaches ; nothing else changes. The abstract operation merges exactly those two sets. The pointer graph stays acyclic because is a root, so no path leads from back into 's tree. True.- Path compression re-points (on the path from to root ) directly to . Each reached before and reaches after, and every node below still reaches . Roots are unchanged, so the partition is unchanged. Halving and splitting re-point a node to its grandparent, an ancestor on the same root path — same argument.
- Union by size/rank only chooses which of two roots goes under the other; either choice gives the same partition.
So correctness is independent of all the optimizations. That is why the bugs in DSU code are almost never wrong answers about connectivity — they are wrong sizes (updating size on a non-root), wrong counts (decrementing count when the roots were equal), and stack overflows.
The inverse-Ackermann bound (statement)
Theorem (Tarjan 1975; Tarjan & van Leeuwen 1984). A sequence of find/union operations on elements, using union by rank (or size) and path compression (or path halving, or path splitting), runs in time, where is a functional inverse of Ackermann's function. Fredman and Saks (1989) proved a matching lower bound in the cell-probe model, so no union-find structure can do asymptotically better.
What is ? CLRS (3rd edition, chapter 21) uses this version of Ackermann's function, defined for integers , :
where means "apply to its argument times". Each level iterates the previous one: (iterated successor is addition), (iterated doubling is exponentiation), is a tower of exponentials, and iterates towers. The inverse is
The values, computed by a script that implements the definition literally:
| for | ||
|---|---|---|
| 0 | 2 | |
| 1 | 3 | |
| 2 | 7 | |
| 3 | 2047 | |
| 4 | — larger than a tower of 2048 twos |
For comparison, already has 620 decimal digits, and applies to that 2048 times. The number of atoms in the observable universe is around . So for every input that will ever exist. Other textbooks define Ackermann's function and its inverse slightly differently (Tarjan's original uses the two-argument , which decreases as grows); the variants differ by small additive constants and none of them exceeds 5 in practice. "Effectively constant, but provably not constant" is the correct summary.
Intuition for why the answer is Ackermann. Path compression makes paths short, and union by rank makes ranks grow slowly. A node on a find path is "expensive" only if its parent's rank is not much larger than its own; each compression gives it a parent of strictly larger rank. Tarjan's analysis groups nodes by how fast their parent's rank is growing relative to their own — first by "parent rank exceeds mine by at least 1", then "by at least of mine", then "by at least ", and so on. Each level of the hierarchy can charge each node only a bounded number of times before the node graduates to the next level, and there are only levels before the parent's rank would exceed , the maximum possible rank. The simpler analysis below uses a single level of this idea with instead of .
Proof sketch of the simpler bound
(iterated logarithm) is the number of times you apply to before the result is at most 1:
| 1 | 0 |
| 2 | 1 |
| 3 – 4 | 2 |
| 5 – 16 | 3 |
| 17 – 65,536 | 4 |
| 65,537 – | 5 |
Theorem (Hopcroft & Ullman 1973). With union by rank and path compression, operations on elements cost .
We use three facts about ranks (union by rank; path compression never changes ranks).
- (R1) For a non-root , , and this stays true forever. Linking puts a root under a root of rank at least as large and bumps on ties; compression gives a new parent that was an ancestor, hence of even larger rank. A non-root's own rank never changes again.
- (R2) A node of rank had at least nodes in its subtree when it got that rank (shown in the height proof).
- (R3) At most nodes ever have rank : the subtrees from (R2) of two distinct rank- nodes are disjoint (if one were inside the other, by (R1) the ancestor would have larger rank). So ranks are at most .
Rank blocks. Let and , so . Put rank into block if (ranks 0 and 1 go in block 0). Ranks are at most , so there are at most blocks.
Charging. A find(x) walks = root and costs . Charge each visited node either to the operation or to the node:
- to the operation if is the root or the root's child, or if 's rank is in a different block from 's rank. Ranks strictly increase along the path (R1), so the block changes at most times. Each find gets at most such charges.
- to the node otherwise — its parent is in the same block, and is not the root's child, so compression is about to give a new parent (the root) of strictly larger rank than its old parent.
Counting node charges. Fix block , ranks in . Each node charge to a node in block strictly increases its parent's rank, and once the parent's rank leaves block the node is never node-charged again. So each node in block is charged at most times. By (R3) the number of nodes with rank in block is at most
So block absorbs fewer than node charges. Over at most blocks: . Adding the operation charges, , gives the theorem.
The structure of this proof — "a node is charged only while its parent's rank is close to its own, and each charge pushes the parent's rank up" — is exactly the seed of Tarjan's analysis, which replaces the single tower by the whole Ackermann hierarchy.
Complexity
| Operation | By size only | By size + compression |
|---|---|---|
find, union, connected | worst case | amortized; a single call can be |
| operations | ||
count, set_size | / | / |
| Memory | integers | integers |
Best case: everything is one hop from its root, per operation. Amortized is the honest description of the compressed version: one find can walk links (the deepest node of a binomial tree), but that walk flattens the path so later operations are cheap. If you need a hard per-operation bound — real-time systems, or rollback — use union by size alone.
Constants and cache behaviour. The structure is two flat integer arrays, which is ideal: in C++ or Java, operations on elements take a few tens of milliseconds. The cost that remains is cache misses: each hop is a dependent load to an essentially random index, so a find on a large, cold structure costs one cache miss per hop. Compression and halving matter in practice mostly because they cut hops, and therefore misses. Storing parent as 32-bit integers rather than 64-bit pointers halves the memory traffic. A common trick is to store size in the parent array for roots as a negative number (parent[r] = -size), which keeps one array instead of two.
In Python the constant factor dominates: function call overhead makes each find several hundred nanoseconds. Inline the find loop in hot paths, or use the iterative version on plain lists; never recurse.
Implementation
Canonical DSU: union by size, path compression, component count
The same test data in all four languages: ten elements, seven unions, a redundant union, size and count checks, and a 200,000-element chain to prove the iterative find never recurses.
class DSU:
"""Disjoint-set union with union by size and two-pass path compression."""
def __init__(self, n: int) -> None:
self.parent = list(range(n))
self.size = [1] * n
self.count = n # number of disjoint sets
def find(self, x: int) -> int:
root = x
while self.parent[root] != root: # pass 1: find the root
root = self.parent[root]
while self.parent[x] != root: # pass 2: point the path at it
self.parent[x], x = root, self.parent[x]
return root
def union(self, a: int, b: int) -> bool:
ra, rb = self.find(a), self.find(b)
if ra == rb:
return False
if self.size[ra] < self.size[rb]:
ra, rb = rb, ra
self.parent[rb] = ra # smaller tree under larger
self.size[ra] += self.size[rb]
self.count -= 1
return True
def connected(self, a: int, b: int) -> bool:
return self.find(a) == self.find(b)
def set_size(self, x: int) -> int:
return self.size[self.find(x)]
def main() -> None:
d = DSU(10)
for a, b in [(0, 1), (2, 3), (1, 3), (4, 5), (6, 7), (5, 7), (8, 9)]:
assert d.union(a, b)
assert not d.union(0, 3) # already connected
assert d.count == 3 # {0,1,2,3} {4,5,6,7} {8,9}
assert d.set_size(2) == 4 and d.set_size(9) == 2
assert d.connected(0, 2) and not d.connected(0, 4)
assert d.union(3, 7) and d.count == 2 and d.set_size(6) == 8
big = DSU(200_000) # long chains: no recursion anywhere
for i in range(199_999):
big.union(i, i + 1)
assert big.count == 1 and big.set_size(123_456) == 200_000
print("DSU ok")
main()
public class UnionFind {
private final int[] parent;
private final int[] size;
private int count;
public UnionFind(int n) {
parent = new int[n];
size = new int[n];
for (int i = 0; i < n; i++) { parent[i] = i; size[i] = 1; }
count = n;
}
public int find(int x) {
int root = x;
while (parent[root] != root) root = parent[root]; // pass 1
while (parent[x] != root) { // pass 2
int next = parent[x];
parent[x] = root;
x = next;
}
return root;
}
public boolean union(int a, int b) {
int ra = find(a), rb = find(b);
if (ra == rb) return false;
if (size[ra] < size[rb]) { int t = ra; ra = rb; rb = t; }
parent[rb] = ra; // smaller under larger
size[ra] += size[rb];
count--;
return true;
}
public boolean connected(int a, int b) { return find(a) == find(b); }
public int setSize(int x) { return size[find(x)]; }
public int count() { return count; }
private static void check(boolean cond, String msg) {
if (!cond) throw new AssertionError(msg);
}
public static void main(String[] args) {
UnionFind d = new UnionFind(10);
int[][] pairs = {{0, 1}, {2, 3}, {1, 3}, {4, 5}, {6, 7}, {5, 7}, {8, 9}};
for (int[] p : pairs) check(d.union(p[0], p[1]), "union should merge");
check(!d.union(0, 3), "already connected");
check(d.count() == 3, "count 3");
check(d.setSize(2) == 4 && d.setSize(9) == 2, "sizes");
check(d.connected(0, 2) && !d.connected(0, 4), "connectivity");
check(d.union(3, 7) && d.count() == 2 && d.setSize(6) == 8, "merge to 8");
UnionFind big = new UnionFind(200_000);
for (int i = 0; i < 199_999; i++) big.union(i, i + 1);
check(big.count() == 1 && big.setSize(123_456) == 200_000, "big chain");
System.out.println("DSU ok");
}
}
#include <cassert>
#include <iostream>
#include <numeric>
#include <utility>
#include <vector>
class DSU {
public:
explicit DSU(int n) : parent_(n), size_(n, 1), count_(n) {
std::iota(parent_.begin(), parent_.end(), 0);
}
int find(int x) {
int root = x;
while (parent_[root] != root) root = parent_[root]; // pass 1
while (parent_[x] != root) { // pass 2
int next = parent_[x];
parent_[x] = root;
x = next;
}
return root;
}
bool unite(int a, int b) {
int ra = find(a), rb = find(b);
if (ra == rb) return false;
if (size_[ra] < size_[rb]) std::swap(ra, rb);
parent_[rb] = ra; // smaller under larger
size_[ra] += size_[rb];
--count_;
return true;
}
bool connected(int a, int b) { return find(a) == find(b); }
int set_size(int x) { return size_[find(x)]; }
int count() const { return count_; }
private:
std::vector<int> parent_, size_;
int count_;
};
int main() {
DSU d(10);
const std::vector<std::pair<int, int>> pairs = {{0, 1}, {2, 3}, {1, 3}, {4, 5}, {6, 7}, {5, 7}, {8, 9}};
for (auto [a, b] : pairs) assert(d.unite(a, b));
assert(!d.unite(0, 3));
assert(d.count() == 3);
assert(d.set_size(2) == 4 && d.set_size(9) == 2);
assert(d.connected(0, 2) && !d.connected(0, 4));
assert(d.unite(3, 7) && d.count() == 2 && d.set_size(6) == 8);
DSU big(200000);
for (int i = 0; i < 199999; ++i) big.unite(i, i + 1);
assert(big.count() == 1 && big.set_size(123456) == 200000);
std::cout << "DSU ok\n";
}
class DSU {
private parent: Int32Array;
private size: Int32Array;
count: number;
constructor(n: number) {
this.parent = new Int32Array(n);
this.size = new Int32Array(n).fill(1);
for (let i = 0; i < n; i++) this.parent[i] = i;
this.count = n;
}
find(x: number): number {
let root = x;
while (this.parent[root] !== root) root = this.parent[root]; // pass 1
while (this.parent[x] !== root) { // pass 2
const next = this.parent[x];
this.parent[x] = root;
x = next;
}
return root;
}
union(a: number, b: number): boolean {
let ra = this.find(a), rb = this.find(b);
if (ra === rb) return false;
if (this.size[ra] < this.size[rb]) [ra, rb] = [rb, ra];
this.parent[rb] = ra; // smaller under larger
this.size[ra] += this.size[rb];
this.count--;
return true;
}
connected(a: number, b: number): boolean {
return this.find(a) === this.find(b);
}
setSize(x: number): number {
return this.size[this.find(x)];
}
}
function check(cond: boolean, msg: string): void {
if (!cond) throw new Error(msg);
}
const d = new DSU(10);
for (const [a, b] of [[0, 1], [2, 3], [1, 3], [4, 5], [6, 7], [5, 7], [8, 9]]) {
check(d.union(a, b), "union should merge");
}
check(!d.union(0, 3), "already connected");
check(d.count === 3, "count 3");
check(d.setSize(2) === 4 && d.setSize(9) === 2, "sizes");
check(d.connected(0, 2) && !d.connected(0, 4), "connectivity");
check(d.union(3, 7) && d.count === 2 && d.setSize(6) === 8, "merge to 8");
const big = new DSU(200_000);
for (let i = 0; i < 199_999; i++) big.union(i, i + 1);
check(big.count === 1 && big.setSize(123_456) === 200_000, "big chain");
console.log("DSU ok");
Weighted (potential) DSU
Sometimes the facts are not "a and b are related" but "a and b are related by this amount": ; "a weighs 5 more than b"; . A weighted DSU stores, for each node, its offset to its parent: . The value of a root is a free unknown; every other value in its set is determined relative to it. Following the path to the root and summing offsets gives . Two elements in the same set have a known difference; elements in different sets have none.
- Find with compression must keep the sums right: when is re-pointed to the root, its
diffbecomes the sum along the old path. Process the path from the node nearest the root downward, so each node's parent has already been fixed. - Union asserting : after the finds, and . Attaching under needs . If already, the fact is either consistent () or a contradiction — which is how these problems detect impossible input.
The same structure works for any group operation: addition (offsets), multiplication (ratios — Evaluate Division), XOR (parity — see the bipartite variant below), even composition of permutations. You need an identity, an inverse and associativity; commutativity is not required if you are careful about order.
class WeightedDSU:
"""Maintains val[a] - val[b] for every pair a, b in the same set."""
def __init__(self, n: int) -> None:
self.parent = list(range(n))
self.size = [1] * n
self.diff = [0] * n # val[x] - val[parent[x]]
def find(self, x: int) -> int:
path = []
while self.parent[x] != x:
path.append(x)
x = self.parent[x]
root = x
for node in reversed(path): # nearest-to-root first
p = self.parent[node]
if p != root:
self.diff[node] += self.diff[p] # p already points at root
self.parent[node] = root
return root
def union(self, a: int, b: int, d: int) -> bool:
"""Record val[a] - val[b] == d. Returns False on a contradiction."""
ra, rb = self.find(a), self.find(b)
if ra == rb:
return self.diff[a] - self.diff[b] == d
if self.size[ra] < self.size[rb]: # swap roles: val[b] - val[a] == -d
ra, rb, a, b, d = rb, ra, b, a, -d
self.parent[rb] = ra
self.diff[rb] = self.diff[a] - self.diff[b] - d
self.size[ra] += self.size[rb]
return True
def difference(self, a: int, b: int) -> int | None:
"""val[a] - val[b], or None if a and b are unrelated."""
if self.find(a) != self.find(b):
return None
return self.diff[a] - self.diff[b]
def main() -> None:
w = WeightedDSU(6)
assert w.union(0, 1, 3) # x0 - x1 = 3
assert w.union(1, 2, 4) # x1 - x2 = 4
assert w.difference(0, 2) == 7
assert w.union(3, 4, -2) # x3 - x4 = -2
assert w.difference(0, 3) is None
assert w.union(2, 3, 1) # x2 - x3 = 1, joins the two groups
assert w.difference(0, 4) == 6 and w.difference(4, 0) == -6
assert not w.union(0, 2, 5) # contradicts x0 - x2 = 7
assert w.union(0, 2, 7) # consistent, no change
assert w.difference(5, 5) == 0 and w.difference(5, 0) is None
print("weighted DSU ok")
main()
public class WeightedDSU {
private final int[] parent, size;
private final long[] diff; // val[x] - val[parent[x]]
public WeightedDSU(int n) {
parent = new int[n];
size = new int[n];
diff = new long[n];
for (int i = 0; i < n; i++) { parent[i] = i; size[i] = 1; }
}
public int find(int x) {
int len = 0, root = x;
while (parent[root] != root) { root = parent[root]; len++; }
int[] path = new int[len];
for (int i = 0, y = x; i < len; i++, y = parent[y]) path[i] = y;
for (int i = len - 1; i >= 0; i--) { // nearest-to-root first
int node = path[i], p = parent[node];
if (p != root) {
diff[node] += diff[p];
parent[node] = root;
}
}
return root;
}
/** Record val[a] - val[b] == d; false on a contradiction. */
public boolean union(int a, int b, long d) {
int ra = find(a), rb = find(b);
if (ra == rb) return diff[a] - diff[b] == d;
if (size[ra] < size[rb]) {
int t = ra; ra = rb; rb = t;
t = a; a = b; b = t;
d = -d;
}
parent[rb] = ra;
diff[rb] = diff[a] - diff[b] - d;
size[ra] += size[rb];
return true;
}
/** val[a] - val[b], or null when unrelated. */
public Long difference(int a, int b) {
if (find(a) != find(b)) return null;
return diff[a] - diff[b];
}
private static void check(boolean cond, String msg) {
if (!cond) throw new AssertionError(msg);
}
public static void main(String[] args) {
WeightedDSU w = new WeightedDSU(6);
check(w.union(0, 1, 3), "x0 - x1 = 3");
check(w.union(1, 2, 4), "x1 - x2 = 4");
check(w.difference(0, 2) == 7L, "x0 - x2");
check(w.union(3, 4, -2), "x3 - x4 = -2");
check(w.difference(0, 3) == null, "unrelated");
check(w.union(2, 3, 1), "join groups");
check(w.difference(0, 4) == 6L && w.difference(4, 0) == -6L, "x0 - x4");
check(!w.union(0, 2, 5), "contradiction");
check(w.union(0, 2, 7), "consistent");
check(w.difference(5, 5) == 0L && w.difference(5, 0) == null, "singleton");
System.out.println("weighted DSU ok");
}
}
#include <cassert>
#include <cstdint>
#include <iostream>
#include <numeric>
#include <optional>
#include <utility>
#include <vector>
class WeightedDSU {
public:
explicit WeightedDSU(int n) : parent_(n), size_(n, 1), diff_(n, 0) {
std::iota(parent_.begin(), parent_.end(), 0);
}
int find(int x) {
std::vector<int> path;
while (parent_[x] != x) { path.push_back(x); x = parent_[x]; }
const int root = x;
for (auto it = path.rbegin(); it != path.rend(); ++it) { // nearest-to-root first
int node = *it, p = parent_[node];
if (p != root) {
diff_[node] += diff_[p];
parent_[node] = root;
}
}
return root;
}
// Record val[a] - val[b] == d; false on a contradiction.
bool unite(int a, int b, std::int64_t d) {
int ra = find(a), rb = find(b);
if (ra == rb) return diff_[a] - diff_[b] == d;
if (size_[ra] < size_[rb]) { std::swap(ra, rb); std::swap(a, b); d = -d; }
parent_[rb] = ra;
diff_[rb] = diff_[a] - diff_[b] - d;
size_[ra] += size_[rb];
return true;
}
std::optional<std::int64_t> difference(int a, int b) {
if (find(a) != find(b)) return std::nullopt;
return diff_[a] - diff_[b];
}
private:
std::vector<int> parent_, size_;
std::vector<std::int64_t> diff_; // val[x] - val[parent[x]]
};
int main() {
WeightedDSU w(6);
assert(w.unite(0, 1, 3));
assert(w.unite(1, 2, 4));
assert(w.difference(0, 2) == 7);
assert(w.unite(3, 4, -2));
assert(!w.difference(0, 3).has_value());
assert(w.unite(2, 3, 1));
assert(w.difference(0, 4) == 6 && w.difference(4, 0) == -6);
assert(!w.unite(0, 2, 5));
assert(w.unite(0, 2, 7));
assert(w.difference(5, 5) == 0 && !w.difference(5, 0).has_value());
std::cout << "weighted DSU ok\n";
}
class WeightedDSU {
private parent: number[];
private size: number[];
private diff: number[]; // val[x] - val[parent[x]]
constructor(n: number) {
this.parent = Array.from({ length: n }, (_, i) => i);
this.size = new Array(n).fill(1);
this.diff = new Array(n).fill(0);
}
find(x: number): number {
const path: number[] = [];
while (this.parent[x] !== x) {
path.push(x);
x = this.parent[x];
}
const root = x;
for (let i = path.length - 1; i >= 0; i--) { // nearest-to-root first
const node = path[i], p = this.parent[node];
if (p !== root) {
this.diff[node] += this.diff[p];
this.parent[node] = root;
}
}
return root;
}
/** Record val[a] - val[b] === d; false on a contradiction. */
union(a: number, b: number, d: number): boolean {
let ra = this.find(a), rb = this.find(b);
if (ra === rb) return this.diff[a] - this.diff[b] === d;
if (this.size[ra] < this.size[rb]) {
[ra, rb] = [rb, ra];
[a, b] = [b, a];
d = -d;
}
this.parent[rb] = ra;
this.diff[rb] = this.diff[a] - this.diff[b] - d;
this.size[ra] += this.size[rb];
return true;
}
difference(a: number, b: number): number | null {
if (this.find(a) !== this.find(b)) return null;
return this.diff[a] - this.diff[b];
}
}
function check(cond: boolean, msg: string): void {
if (!cond) throw new Error(msg);
}
const w = new WeightedDSU(6);
check(w.union(0, 1, 3), "x0 - x1 = 3");
check(w.union(1, 2, 4), "x1 - x2 = 4");
check(w.difference(0, 2) === 7, "x0 - x2");
check(w.union(3, 4, -2), "x3 - x4 = -2");
check(w.difference(0, 3) === null, "unrelated");
check(w.union(2, 3, 1), "join groups");
check(w.difference(0, 4) === 6 && w.difference(4, 0) === -6, "x0 - x4");
check(!w.union(0, 2, 5), "contradiction");
check(w.union(0, 2, 7), "consistent");
check(w.difference(5, 5) === 0 && w.difference(5, 0) === null, "singleton");
console.log("weighted DSU ok");
For ratios (Evaluate Division, currency conversion, unit systems) replace with and with : store , multiply along paths, and attach with for the fact . The practice ladder's Evaluate Division solution is exactly this. The "accounts merge with ratios" pattern — a set of exchange rates where you must answer conversions or detect an inconsistent rate (an arbitrage cycle whose product is not 1) — is the same code with a tolerance on the consistency check, because floating-point products will not be exactly equal.
Variant: DSU for bipartiteness (parity)
A graph is bipartite iff its vertices can be 2-coloured so every edge joins different colours. Store — the weighted DSU over the group . An edge is the fact . If and are already in one set and their parities to the root are equal, the edge closes an odd cycle and the graph stops being bipartite. Unlike BFS 2-colouring, this works incrementally: after each edge, you know whether the graph so far is bipartite.
class ParityDSU:
def __init__(self, n: int) -> None:
self.parent = list(range(n))
self.size = [1] * n
self.par = [0] * n # colour[x] xor colour[parent[x]]
def find(self, x: int) -> tuple[int, int]:
"""Return (root, colour[x] xor colour[root]), compressing the path."""
path = []
while self.parent[x] != x:
path.append(x)
x = self.parent[x]
root = x
for node in reversed(path):
p = self.parent[node]
if p != root:
self.par[node] ^= self.par[p]
self.parent[node] = root
return root, (self.par[path[0]] if path else 0)
def add_edge(self, u: int, v: int) -> bool:
"""Require different colours. Returns False if this closes an odd cycle."""
(ru, pu), (rv, pv) = self.find(u), self.find(v)
if ru == rv:
return pu != pv
if self.size[ru] < self.size[rv]:
ru, rv, pu, pv = rv, ru, pv, pu
self.parent[rv] = ru
self.par[rv] = pu ^ pv ^ 1 # makes colour[u] xor colour[v] == 1
self.size[ru] += self.size[rv]
return True
def main() -> None:
p = ParityDSU(5)
assert p.add_edge(0, 1) and p.add_edge(1, 2) and p.add_edge(2, 3) # path 0-1-2-3
assert p.add_edge(3, 0) # 4-cycle: even, still bipartite
assert not p.add_edge(0, 2) # 0-1-2-0 is a triangle: odd cycle
q = ParityDSU(4)
assert q.add_edge(0, 1) and q.add_edge(2, 3) and q.add_edge(1, 2)
_, c0 = q.find(0)
_, c3 = q.find(3)
assert c0 != c3 # 0-1-2-3 path: ends have opposite colours
print("parity DSU ok")
main()
Variant: rollback DSU
Path compression rewrites many pointers per call, which makes undo expensive. Rollback DSU drops compression and keeps union by size, so each union changes exactly one parent pointer and one size. Push a record of the change onto a stack; rollback(snapshot) pops records and restores them. Find is worst case (the height bound needs no amortization, which is exactly what makes undo safe), union is , rollback is per undone union.
class RollbackDSU:
"""Union by size, no path compression, undo in LIFO order."""
def __init__(self, n: int) -> None:
self.parent = list(range(n))
self.size = [1] * n
self.count = n
self.history: list[int] = [] # attached root per union, -1 for no-ops
def find(self, x: int) -> int:
while self.parent[x] != x:
x = self.parent[x]
return x
def union(self, a: int, b: int) -> bool:
ra, rb = self.find(a), self.find(b)
if ra == rb:
self.history.append(-1)
return False
if self.size[ra] < self.size[rb]:
ra, rb = rb, ra
self.parent[rb] = ra
self.size[ra] += self.size[rb]
self.count -= 1
self.history.append(rb)
return True
def snapshot(self) -> int:
return len(self.history)
def rollback(self, snap: int) -> None:
while len(self.history) > snap:
rb = self.history.pop()
if rb == -1:
continue
ra = self.parent[rb]
self.size[ra] -= self.size[rb]
self.parent[rb] = rb
self.count += 1
def offline_dynamic_connectivity(n: int, ops: list[tuple[str, int, int]]) -> list[int]:
"""ops: ('add', u, v), ('remove', u, v), ('count', 0, 0). Returns component counts.
Each edge lives on a time interval; insert it into O(log q) segment-tree nodes,
then DFS the tree, applying edges on the way down and rolling back on the way up.
"""
q = len(ops)
tree: list[list[tuple[int, int]]] = [[] for _ in range(4 * max(q, 1))]
def insert(node: int, lo: int, hi: int, l: int, r: int, e: tuple[int, int]) -> None:
if r < lo or hi < l:
return
if l <= lo and hi <= r:
tree[node].append(e)
return
mid = (lo + hi) // 2
insert(2 * node, lo, mid, l, r, e)
insert(2 * node + 1, mid + 1, hi, l, r, e)
start: dict[tuple[int, int], int] = {}
for t, (kind, u, v) in enumerate(ops):
e = (min(u, v), max(u, v))
if kind == "add":
start[e] = t
elif kind == "remove":
insert(1, 0, q - 1, start.pop(e), t - 1, e)
for e, t in start.items():
insert(1, 0, q - 1, t, q - 1, e)
dsu, answers = RollbackDSU(n), []
def dfs(node: int, lo: int, hi: int) -> None:
snap = dsu.snapshot()
for u, v in tree[node]:
dsu.union(u, v)
if lo == hi:
if ops[lo][0] == "count":
answers.append(dsu.count)
else:
mid = (lo + hi) // 2
dfs(2 * node, lo, mid)
dfs(2 * node + 1, mid + 1, hi)
dsu.rollback(snap)
if q:
dfs(1, 0, q - 1)
return answers
def brute(n: int, ops: list[tuple[str, int, int]]) -> list[int]:
edges: set[tuple[int, int]] = set()
out = []
for kind, u, v in ops:
e = (min(u, v), max(u, v))
if kind == "add":
edges.add(e)
elif kind == "remove":
edges.discard(e)
else:
d = RollbackDSU(n)
for a, b in edges:
d.union(a, b)
out.append(d.count)
return out
def main() -> None:
d = RollbackDSU(5)
s0 = d.snapshot()
d.union(0, 1); d.union(2, 3)
s1 = d.snapshot()
d.union(1, 3); d.union(0, 2) # second one is a no-op
assert d.count == 2 and d.find(3) == d.find(0)
d.rollback(s1)
assert d.count == 3 and d.find(3) != d.find(0) and d.find(2) == d.find(3)
d.rollback(s0)
assert d.count == 5 and d.size == [1] * 5
import random
rng = random.Random(7)
for _ in range(200):
n, ops, live = 6, [], set()
for _ in range(25):
r = rng.random()
if r < 0.4:
u, v = rng.sample(range(n), 2)
e = (min(u, v), max(u, v))
if e not in live:
live.add(e); ops.append(("add", u, v))
elif r < 0.6 and live:
e = rng.choice(sorted(live))
live.remove(e); ops.append(("remove", e[1], e[0]))
else:
ops.append(("count", 0, 0))
assert offline_dynamic_connectivity(n, ops) == brute(n, ops)
print("rollback DSU and offline dynamic connectivity ok")
main()
The second function is the main reason rollback DSU exists: offline dynamic connectivity. When edges are both added and removed and all operations are known in advance, each edge is alive on an interval of time. Insert that interval into a segment tree over time ( nodes, as in Segment Trees in Depth), then DFS the tree: apply a node's edges when entering, answer queries at leaves, roll back when leaving. Total . The randomized test above checks it against a brute force on 200 random scripts.
Variant: Kruskal in eight lines (preview)
Sort edges by weight; accept an edge iff its endpoints are in different sets. The next lesson proves why this yields a minimum spanning tree.
def kruskal(n: int, edges: list[tuple[int, int, int]]) -> int:
parent = list(range(n))
def find(x: int) -> int:
while parent[x] != x:
parent[x] = parent[parent[x]] # path halving
x = parent[x]
return x
total = used = 0
for w, u, v in sorted((w, u, v) for u, v, w in edges):
ru, rv = find(u), find(v)
if ru != rv:
parent[ru] = rv
total += w
used += 1
assert used == n - 1, "graph is disconnected"
return total
edges = [(0, 1, 7), (0, 3, 5), (1, 2, 8), (1, 3, 9), (1, 4, 4), (2, 4, 3),
(3, 4, 12), (3, 5, 6), (4, 5, 11), (4, 6, 10), (5, 6, 13), (2, 6, 14)]
assert kruskal(7, edges) == 35
print("kruskal preview ok")
This omits union by size for brevity; halving alone still gives amortized here. Production code should use the full DSU.
Variant: percolation, the classic simulation
Open sites of an grid at random until the top connects to the bottom. Two virtual nodes — top joined to every open cell in row 0, bottom to every open cell in row — reduce "does it percolate?" to one connected(top, bottom) call. Sedgewick and Wayne use this as their motivating example; the threshold fraction of open sites converges to about for site percolation on the square lattice.
import random
def percolation_fraction(n: int, rng: random.Random) -> float:
top, bottom = n * n, n * n + 1
parent = list(range(n * n + 2))
size = [1] * (n * n + 2)
def find(x: int) -> int:
while parent[x] != x:
parent[x] = parent[parent[x]]
x = parent[x]
return x
def union(a: int, b: int) -> None:
ra, rb = find(a), find(b)
if ra != rb:
if size[ra] < size[rb]:
ra, rb = rb, ra
parent[rb] = ra
size[ra] += size[rb]
open_ = [False] * (n * n)
order = list(range(n * n))
rng.shuffle(order)
for k, cell in enumerate(order, 1):
open_[cell] = True
r, c = divmod(cell, n)
if r == 0:
union(cell, top)
if r == n - 1:
union(cell, bottom)
for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
rr, cc = r + dr, c + dc
if 0 <= rr < n and 0 <= cc < n and open_[rr * n + cc]:
union(cell, rr * n + cc)
if find(top) == find(bottom):
return k / (n * n)
return 1.0
rng = random.Random(42)
trials = [percolation_fraction(40, rng) for _ in range(60)]
mean = sum(trials) / len(trials)
assert 0.55 < mean < 0.64, mean # converges to ~0.5927 as n grows
print(f"estimated threshold {mean:.3f}")
Real-world uses
- Kruskal's algorithm and everything built on it. Minimum spanning trees for network design, single-linkage clustering (stop Kruskal when clusters remain), and bottleneck-path queries. See the next lesson, Minimum Spanning Trees, and the MST section of Greedy Algorithms.
- Connected-component labelling in images. The classic two-pass algorithm (Rosenfeld and Pfaltz, 1966) scans pixels, assigns provisional labels, records "label 7 touches label 3" as unions, and resolves them in a second pass. OpenCV's
connectedComponentsoffers several such algorithms (Wu's SAUF, Grana's BBDT, Bolelli's Spaghetti), all of which keep label equivalences in a union-find array. Medical imaging, OCR and blob detection in robotics run this on every frame. - Percolation and physics simulations. The Hoshen–Kopelman algorithm (1976) for labelling clusters on a lattice is union-find specialized to grids; it is a standard tool in statistical physics and porous-media simulation.
- Network connectivity. "Can host A reach host B after this link comes up?" with links only being added is DSU. Real networks also lose links, so production systems recompute or use dynamic structures — but offline analysis of link logs, and incremental topology checks in SDN controllers, are union-find problems. See The Network Layer.
- Type inference by unification (Hindley–Milner). Type checkers for ML, OCaml, Haskell and Rust-style inference represent each unknown type as a variable and each constraint "these two types are equal" as a unification. Unifying two variables is a union; looking up what a variable currently stands for is a find. Efficient unification algorithms (Huet 1976; Martelli and Montanari 1982) are near-linear precisely because they use union-find. Compilers in this family implement type variables as mutable cells that get linked to each other on unification, with a "follow the links" representative lookup — union-find in all but name.
- Equivalence of types and symbols. Galler and Fischer's original motivation: Fortran
EQUIVALENCEstatements declare variables that share storage, and the compiler must compute the resulting classes. Structural type-equivalence checking (are these two recursive type definitions the same?) uses union-find over type nodes, merging optimistically and checking for contradictions — the same algorithm as DFA minimization by merging states (Hopcroft–Karp's near-linear DFA equivalence test, 1971). - Pointer analysis in compilers. Steensgaard's points-to analysis (POPL 1996) runs in almost linear time by treating assignments as unifications of abstract memory locations in a union-find structure. It is the fast, imprecise end of alias analysis in many static analyzers.
- Query optimizers. Predicates like
a.x = b.y AND b.y = c.zimplya.x = c.z; planners compute equivalence classes of columns so they can choose join orders and push predicates (PostgreSQL's planner calls these EquivalenceClasses). The abstract problem is incremental equivalence, the DSU problem, whatever data structure a given planner uses internally. See Query Planning & Optimization. - Data deduplication and entity resolution. "Merge records that share an email, a phone or a device id" is the Accounts Merge pattern at scale: emit pairwise matches, union them, read off the groups. Large-scale versions run union-find in distributed form (for example in Spark jobs), alternating local union-find with merges of partial results.
- Maze generation. Randomized Kruskal: start with all walls up, visit walls in random order, knock a wall down if the cells on either side are not yet connected. The result is a uniformly random-looking perfect maze (exactly one path between any two cells), because the accepted walls form a spanning tree.
Pitfalls & edge cases
- Updating size or rank on the wrong node. Only root entries are meaningful.
size[a] += size[b]instead ofsize[ra] += size[rb]gives garbage sizes while connectivity stays correct, so tests that only check connectivity miss it. - Decrementing
countwhen the roots were equal. Return early onra == rbbefore touching the counter. - Comparing parents instead of roots.
parent[a] == parent[b]is not "same set". Always comparefind(a) == find(b). After full compression they happen to coincide, which hides the bug in small tests. - Recursive find without balancing. Path compression alone on a chain recurses levels; Python dies at 1000, Java with a
StackOverflowErroraround to depending on stack size. Use the iterative two-pass or halving loop. - Rollback with path compression. Compression rewrites pointers that the undo log does not know about. Rollback DSU must not compress.
- Using the weighted DSU's
diffbeforefind.diff[x]is relative toparent[x], not the root, untilfind(x)has compressed . Callfindfirst, every time. - Floating-point ratios. Products of doubles drift; check consistency with a relative tolerance, not
==. Or work with logarithms (sums) or exact fractions when inputs are small. - Element ids that are not . Strings, coordinates, emails: map them to indices with a hash map first, or use a dict-based DSU where
parent.setdefault(x, x)creates elements lazily. - Grid encoding. Cell is
r * cols + c, notr * rows + c. Virtual nodes (top, bottom, "border") go at the end: indicesrows * cols,rows * cols + 1. - Deletions. Union-find cannot split a set. "Remove an edge" online requires a different structure; offline, reverse time (process deletions as additions backwards) or use the segment-tree-over-time trick.
- Union by rank with compression is not "by height". Do not try to recompute heights after compression; ranks are deliberately stale upper bounds.
Variations
- Union by rank vs size vs index. Rank and size give identical bounds. Linking by random index (randomized linking) gives the same bound in expectation (Goel, Khanna, Larkin, Tarjan, SODA 2014), and is handy when you want neither array.
- Path halving / splitting / full compression. Same asymptotics with union by rank or size; halving is usually fastest and simplest.
- Weighted / potential DSU. Offsets, ratios, parities — any group. Used for systems of difference constraints that are equalities, relative positions, and consistency checks.
- Rollback DSU for divide and conquer and offline dynamic connectivity; persistent DSU (a persistent array for
parent, per operation) when you need to query old versions. - DSU with extra per-set data. Store a min, max, sum, list of members or a small-to-large merged set at each root. Merging member lists small-into-large costs total, the small-to-large technique ("DSU on tree" in contest slang is related).
- "Next free slot" DSU.
parent[i]points to the next unused index at or after ; claiming a slot unions it with . Answers "first available seat/day/position ≥ x" in near-constant time — used in scheduling problems with deadlines. - Dynamic connectivity with deletions. Holm, de Lichtenberg and Thorup (2001) maintain connectivity under edge insertions and deletions in amortized per update; link-cut trees (Sleator–Tarjan) handle forests with path queries. These are what you reach for when groups must split online.
- Concurrent union-find. Lock-free versions using compare-and-swap on parent pointers exist (Anderson and Woll, 1991; Jayanti and Tarjan, 2016) and are used in parallel connected-components codes. See Lock-Free Data Structures.
- Distributed connected components. At cluster scale, label propagation or the "hash-to-min" family replace pointer chasing; union-find still runs inside each partition.
Practice ladder
Problems are described in my own words; follow the link for the official statement.
1. Number of Provinces (LeetCode 547) — An adjacency matrix of friendships; count the friend groups. Teaches the plain DSU with a component counter.
Hint
Start with count = n; every successful union decrements it. Only scan the upper triangle of the matrix.
2. Find if Path Exists in Graph (LeetCode 1971) — Edge list plus a source and a target. Teaches DSU as an alternative to BFS when you only need reachability.
Hint
Union every edge, then compare find(source) and find(destination). No adjacency list needed.
3. Redundant Connection (LeetCode 684) — A tree plus one extra edge; return the extra edge that appears last. Teaches cycle detection: an edge whose endpoints already share a root.
Hint
Process edges in order. The first edge whose union returns false is the answer — and because only one edge is extra, it is also the last such edge.
Solution
def find_redundant_connection(edges: list[list[int]]) -> list[int]:
parent = list(range(len(edges) + 1))
def find(x: int) -> int:
while parent[x] != x:
parent[x] = parent[parent[x]]
x = parent[x]
return x
for u, v in edges:
ru, rv = find(u), find(v)
if ru == rv:
return [u, v]
parent[ru] = rv
return []
assert find_redundant_connection([[1, 2], [1, 3], [2, 3]]) == [2, 3]
assert find_redundant_connection([[1, 2], [2, 3], [3, 4], [1, 4], [1, 5]]) == [1, 4]
print("redundant connection ok")
time, space.
4. Satisfiability of Equality Equations (LeetCode 990) — Constraints like a==b and b!=c over single-letter variables. Teaches the two-phase pattern: merge all equalities, then check every inequality.
Hint
Order matters: processing != before all == are merged gives wrong answers. A 26-element DSU is enough.
Solution
def equations_possible(equations: list[str]) -> bool:
parent = list(range(26))
def find(x: int) -> int:
while parent[x] != x:
parent[x] = parent[parent[x]]
x = parent[x]
return x
for e in equations:
if e[1] == "=":
parent[find(ord(e[0]) - 97)] = find(ord(e[3]) - 97)
return all(find(ord(e[0]) - 97) != find(ord(e[3]) - 97) for e in equations if e[1] == "!")
assert not equations_possible(["a==b", "b!=a"])
assert equations_possible(["b==a", "a==b"])
assert equations_possible(["a==b", "b==c", "a==c"])
assert not equations_possible(["a==b", "b!=c", "c==a"])
assert equations_possible(["c==c", "b==d", "x!=z"])
print("equality equations ok")
— linear in the number of equations.
5. Number of Operations to Make Network Connected (LeetCode 1319) — Move cables to connect all computers. Teaches that redundant edges are a resource: with components you need moves and at least cables.
Hint
If len(connections) < n - 1, impossible. Otherwise the answer is components - 1.
6. Road Construction (CSES 1676) — Roads are built one by one; after each, report the number of components and the size of the largest. Teaches union by size with a running maximum, at scale.
Hint
The largest component only changes when a union happens; update best = max(best, size[new_root]). Never recompute from scratch.
7. Accounts Merge (LeetCode 721) — Accounts are lists of emails; two accounts belong to the same person if they share any email. Teaches DSU over records keyed by a shared attribute.
Hint
Map each email to the first account index that mentioned it. When an email is seen again, union the two account indices. Then group emails by the root of their owning account and sort.
Solution
from collections import defaultdict
def accounts_merge(accounts: list[list[str]]) -> list[list[str]]:
parent = list(range(len(accounts)))
def find(x: int) -> int:
while parent[x] != x:
parent[x] = parent[parent[x]]
x = parent[x]
return x
owner: dict[str, int] = {}
for i, acc in enumerate(accounts):
for email in acc[1:]:
if email in owner:
parent[find(i)] = find(owner[email])
else:
owner[email] = i
groups: dict[int, list[str]] = defaultdict(list)
for email, i in owner.items():
groups[find(i)].append(email)
return sorted([accounts[r][0]] + sorted(emails) for r, emails in groups.items())
got = accounts_merge([
["John", "johnsmith@mail.com", "john_newyork@mail.com"],
["John", "johnsmith@mail.com", "john00@mail.com"],
["Mary", "mary@mail.com"],
["John", "johnnybravo@mail.com"],
])
assert got == sorted([
["John", "john00@mail.com", "john_newyork@mail.com", "johnsmith@mail.com"],
["Mary", "mary@mail.com"],
["John", "johnnybravo@mail.com"],
])
print("accounts merge ok")
for total emails, dominated by sorting; the DSU part is near-linear.
8. Smallest String With Swaps (LeetCode 1202) — Index pairs that may be swapped any number of times; produce the lexicographically smallest string. Teaches that swap-closure is an equivalence relation: within a component, any permutation is reachable.
Hint
Group indices by root, sort each group's characters, and write them back into the group's sorted indices.
9. Most Stones Removed with Same Row or Column (LeetCode 947) — Remove stones that share a row or column with another stone. Teaches modelling: union rows with columns, and the answer is stones minus components.
Hint
Treat row and column as nodes (offset columns, e.g. c + 10001). Each stone unions its row and column. Every component of size stones can be reduced to one stone.
10. Evaluate Division (LeetCode 399) — Given ratios between variables, answer ratio queries or report . Teaches the multiplicative weighted DSU.
Hint
Store ratio[x] = val(x) / val(parent[x]). A query in the same set is ratio_to_root(a) / ratio_to_root(b).
Solution
def calc_equation(equations: list[list[str]], values: list[float],
queries: list[list[str]]) -> list[float]:
parent: dict[str, str] = {}
ratio: dict[str, float] = {} # val[x] / val[parent[x]]
def find(x: str) -> str:
path = []
while parent[x] != x:
path.append(x)
x = parent[x]
root = x
for node in reversed(path):
p = parent[node]
if p != root:
ratio[node] *= ratio[p]
parent[node] = root
return root
for (a, b), q in zip(equations, values):
for v in (a, b):
if v not in parent:
parent[v], ratio[v] = v, 1.0
ra, rb = find(a), find(b)
if ra != rb: # want val[a] / val[b] == q
parent[rb] = ra
ratio[rb] = ratio[a] / (ratio[b] * q)
out = []
for a, b in queries:
if a not in parent or b not in parent or find(a) != find(b):
out.append(-1.0)
else:
out.append(ratio[a] / ratio[b])
return out
res = calc_equation([["a", "b"], ["b", "c"]], [2.0, 3.0],
[["a", "c"], ["b", "a"], ["a", "e"], ["a", "a"], ["x", "x"]])
expected = [6.0, 0.5, -1.0, 1.0, -1.0]
assert all(abs(x - y) < 1e-9 for x, y in zip(res, expected)), res
print("evaluate division ok")
Near-linear in equations plus queries.
11. Possible Bipartition (LeetCode 886) — Split people into two groups so no pair of "dislikers" shares a group. Teaches the parity DSU (or the "union each node with the enemies of its enemy" trick).
Hint
Use the ParityDSU above, or keep for each person the first person they dislike and union all their other dislikes with that one; then check no disliked pair shares a root.
12. Swim in Rising Water (LeetCode 778) — A grid of elevations; find the earliest time a path from corner to corner exists. Teaches the "add cells in increasing order until connected" sweep — a bottleneck path, Kruskal in disguise.
Hint
Sort cells by elevation, activate them one at a time, union with active neighbours, stop when find(0) == find(n*n - 1). The current elevation is the answer.
13. Checking Existence of Edge Length Limited Paths (LeetCode 1697) — For each query , is there a path using only edges strictly shorter than limit? Teaches offline processing: sort both queries and edges and sweep one DSU.
Hint
Sort queries by limit, keeping their original index. Add all edges with weight < limit before answering each query.
Solution
def distance_limited_paths_exist(n: int, edge_list: list[list[int]],
queries: list[list[int]]) -> list[bool]:
parent = list(range(n))
def find(x: int) -> int:
while parent[x] != x:
parent[x] = parent[parent[x]]
x = parent[x]
return x
edges = sorted(edge_list, key=lambda e: e[2])
order = sorted(range(len(queries)), key=lambda i: queries[i][2])
ans = [False] * len(queries)
k = 0
for i in order:
p, q, limit = queries[i]
while k < len(edges) and edges[k][2] < limit:
u, v, _ = edges[k]
parent[find(u)] = find(v)
k += 1
ans[i] = find(p) == find(q)
return ans
assert distance_limited_paths_exist(3, [[0, 1, 2], [1, 2, 4], [2, 0, 8], [1, 0, 16]],
[[0, 1, 2], [0, 2, 5]]) == [False, True]
assert distance_limited_paths_exist(5, [[0, 1, 10], [1, 2, 5], [2, 3, 9], [3, 4, 13]],
[[0, 4, 14], [1, 4, 13]]) == [True, False]
print("edge length limited paths ok")
for the sorts plus near-linear DSU work.
14. Redundant Connection II (LeetCode 685) — The directed version: a rooted tree plus one extra directed edge. Teaches case analysis on top of DSU: a node with two parents, a cycle, or both.
Hint
First look for a node with in-degree 2; call its two incoming edges cand1 (earlier) and cand2 (later). Run DSU skipping cand2: if no cycle appears, cand2 is the answer; if a cycle appears, the answer is cand1 (or, if there was no in-degree-2 node, the edge that closed the cycle).
15. Restructuring Company (Codeforces 566D) — Merge single pairs, merge whole index ranges, and ask whether two employees are in the same department. Teaches combining a DSU with a "next unmerged index" pointer so range merges are amortized.
Hint
Keep a second array nxt[i] = the next index not yet merged with . A range merge walks nxt pointers, unions neighbours, and path-compresses nxt, so each index is skipped over at most once.
Common mistakes & interview follow-ups
"What is the complexity?" Say it precisely: with union by size/rank and path compression, amortized per operation, where is the inverse Ackermann function, at most 4 for any realistic . With only one of the two optimizations, (worst case for size/rank, amortized for compression). Do not say "" without qualification; do say "effectively constant".
"Why do you need both optimizations?" Union by size bounds the height at in the worst case; compression makes repeated finds cheap. Either alone is ; together they reach . In an interview, either alone is usually acceptable if you can state the bound.
"Can you delete an element or split a set?" Not with plain union-find. Deleting an element can be faked by giving it a fresh id and leaving a tombstone. Splitting requires dynamic connectivity structures (Holm–de Lichtenberg–Thorup) or link-cut trees; offline, reverse time or use segment tree over time with a rollback DSU.
"How would you undo a union?" Rollback DSU: no compression, union by size, a stack of changed roots. find, undo.
"What if the elements are strings or arrive dynamically?" Hash map from key to index, or a dict-based DSU that creates singletons on first sight.
"What if it does not fit in memory / must be distributed?" Partition the edges, run union-find locally, then merge the partial results (each partition's roots form a smaller graph). Or use iterative label propagation in a dataflow system. Mention that pointer-chasing does not distribute well.
"BFS or DSU for connected components?" Static graph, one pass: BFS/DFS, same and simpler to reason about. Edges arriving over time, interleaved queries, or a Kruskal-style sweep: DSU.
"Is it thread-safe?" No — even find writes because of compression. Use a lock, or a lock-free CAS-based version, or drop compression and accept reads.
Common mistakes interviewers watch for: comparing parent[a] == parent[b]; updating size on non-roots; recursive find on a chain; forgetting that union returning false is information (cycle detection); processing inequalities before all equalities are merged.
Quick quiz
1. With union by size and no path compression, what is the maximum height of a tree containing elements, and which sequence achieves it?
Answer
. Merge equal-size trees repeatedly: pairs, then pairs of pairs, … A binomial tree of 512 nodes has height 9; you cannot reach height 10 without 1024 nodes.
2. After the trace in the Mechanics section (step 7), parent = [0, 0, 0, 0, 0, 4, 4, 4]. Which nodes change parent during find(6), and what is the array afterwards?
Answer
The path is 6 → 4 → 0. Only 6 changes (4 already points at 0). Result: [0, 0, 0, 0, 0, 4, 0, 4].
3. Why can rollback DSU not use path compression?
Answer
Compression changes many parent pointers inside find, and those changes are not recorded, so undoing a union would leave nodes pointing to a root that is no longer their root. Without compression each union changes exactly one pointer and one size, which a stack can undo exactly.
4. In a weighted DSU with facts , , , is the new fact consistent?
Answer
Yes. , so . The union finds both in one set and returns true without changing anything.
5. for practical . Why is it still wrong to call union-find ?
Answer
Because is unbounded — it does grow, just absurdly slowly — and Fredman and Saks proved amortized is a lower bound for any union-find structure in the cell-probe model. It is "effectively constant", not constant; and individual operations can cost .
Further reading / sources
- Cormen, Leiserson, Rivest, Stein, Introduction to Algorithms, 3rd ed., chapter 21 "Data Structures for Disjoint Sets" (the definition and the potential-function proof). The 4th edition covers it in chapter 19.
- Robert Sedgewick and Kevin Wayne, Algorithms, 4th ed., section 1.5 "Case Study: Union-Find" (quick-find, quick-union, weighted quick-union, percolation).
- Robert E. Tarjan, "Efficiency of a Good But Not Linear Set Union Algorithm", JACM 22(2), 1975.
- Robert E. Tarjan and Jan van Leeuwen, "Worst-case Analysis of Set Union Algorithms", JACM 31(2), 1984 (path halving and splitting, linking rules, the compression-only bound).
- John E. Hopcroft and Jeffrey D. Ullman, "Set Merging Algorithms", SIAM Journal on Computing 2(4), 1973 (the bound).
- Bernard A. Galler and Michael J. Fischer, "An Improved Equivalence Algorithm", Communications of the ACM 7(5), 1964.
- Michael Fredman and Michael Saks, "The Cell Probe Complexity of Dynamic Data Structures", STOC 1989 (the lower bound).
- Raimund Seidel and Micha Sharir, "Top-Down Analysis of Path Compression", SIAM Journal on Computing 34(3), 2005 — a shorter modern proof of the bound.
- Bjarne Steensgaard, "Points-to Analysis in Almost Linear Time", POPL 1996.
- cp-algorithms: Disjoint Set Union — parity, offline queries, "DSU with rollback" and many applications.
- Antti Laaksonen, Competitive Programmer's Handbook, chapter 15 "Spanning trees" (union-find structure and Kruskal).
Previous lesson: Shortest Paths · Next lesson: Minimum Spanning Trees: Kruskal, Prim & Borůvka
Related: Module 4 overview: Graphs · Advanced Data Structures · Greedy Algorithms · BFS in Depth · DFS in Depth · Connectivity · Segment Trees in Depth · Complexity Analysis · Matrices & 2D Grids · Course home