This site's tenth Disjoint Set entry, and a fifth structure built as an application on top of Union-Find — but a different kind of application than the other four. Offline Lowest Common Ancestor, Small-to-Large Merging, Kruskal's Reconstruction Tree, and Offline Dynamic Connectivity all use Union-Find's "same set?" answer to answer some other question the caller actually cares about. Here, nobody ever asks a question afterward at all: lay a wall between every pair of adjacent rooms in a grid, shuffle the walls into random order, and knock one down exactly when the two rooms it separates are still in different Union-Find groups — the identical cycle check Kruskal's algorithm runs before accepting an edge into a minimum spanning tree, just with a shuffled order standing in for sorted edge weight, since a maze has nothing to minimize. Once every candidate wall has been tested, the check is retired for good — the finished maze is just a grid with some walls missing, and nothing about it remembers Union-Find was ever involved.
36 rooms, 6 rows by 6 columns. Every wall between adjacent rooms starts standing (the dark cells); the small dark squares at every four-way corner are permanent posts, never candidates for removal. Press Step to test the next wall in this run's random order: if the two rooms it separates are still different colors (different Union-Find groups), the wall comes down and both regions recolor to match; if they're already the same color, the wall flashes amber and stays standing — knocking it down would close a cycle. Press Run to go straight through, or Reset for a fresh shuffle and a fresh maze. Every room ends up exactly one color once a run finishes: every room reachable from every other room, by exactly one path.
Model the grid as a graph: one node per room, one edge per candidate wall between adjacent rooms. A
perfect maze — every room reachable from every other by exactly one path, no isolated pockets, no
loops — is exactly a spanning tree of that graph. Removing a wall means including that edge; leaving
it standing means excluding it. Process the edges in any order and accept one only when
find(a) !== find(b), and the accepted edges can never close a cycle — the same argument
Kruskal's algorithm makes for its own accepted edges, since a
graph with no cycle among n nodes and exactly n − 1 edges is, by definition,
a tree. Every rejected edge's two endpoints were already connected through some other
accepted path, so no room is ever left isolated once every candidate has been tested. The processing
order only changes which spanning tree comes out the other end, never whether the result is a
valid one — Kruskal's MST sorts by weight to find the cheapest
tree; this shuffles instead, because a maze has no weight to be cheap about, only a shape to be
interesting.
Random order matters for a reason distinct from correctness, though: without it, the result is
still a valid spanning tree, just a boring one (see Pitfalls below). Whatever order the 60 candidate
walls on this page's own 6×6 grid arrive in, the run always accepts exactly 36 − 1 = 35
of them and leaves the other 25 standing — a fixed count set by the room total alone, not by luck or
order.
Matches the demo above: plain union-by-rank Union-Find (no rollback, no persistence — every union here is permanent and the structure is thrown away the moment the maze is built) driving a Fisher–Yates shuffle over the candidate wall list:
function generateMaze(rows, cols) {
const id = (r, c) => r * cols + c;
const parent = Array.from({ length: rows * cols }, (_, i) => i);
const rank = new Array(rows * cols).fill(0);
function find(x) {
let root = x;
while (parent[root] !== root) root = parent[root];
while (parent[x] !== root) { const next = parent[x]; parent[x] = root; x = next; }
return root;
}
function union(x, y) {
const rx = find(x), ry = find(y);
if (rx === ry) return false; // already connected — the caller must not remove this wall
if (rank[rx] < rank[ry]) parent[rx] = ry;
else if (rank[rx] > rank[ry]) parent[ry] = rx;
else { parent[ry] = rx; rank[rx]++; }
return true;
}
const walls = [];
for (let r = 0; r < rows; r++) {
for (let c = 0; c < cols; c++) {
if (c + 1 < cols) walls.push([id(r, c), id(r, c + 1)]); // wall to the east
if (r + 1 < rows) walls.push([id(r, c), id(r + 1, c)]); // wall to the south
}
}
for (let i = walls.length - 1; i > 0; i--) { // Fisher–Yates shuffle
const j = Math.floor(Math.random() * (i + 1));
[walls[i], walls[j]] = [walls[j], walls[i]];
}
const removed = [];
for (const [a, b] of walls) {
if (find(a) !== find(b)) { union(a, b); removed.push([a, b]); }
}
return removed; // the maze's open passages — every other candidate wall stays standing
}Skip the cycle check, and every wall comes down. Drop the
find(a) !== find(b) test and accept every candidate unconditionally — on this page's own
6×6 grid that removes all 60 walls, not the 35 a real spanning tree keeps, leaving 0 standing instead
of 25. The rooms are all still "connected," technically, but there's no maze left at all: no dead
ends, no decisions, just an open floor. Verified directly against this page's own grid-and-walls
generator, not just reasoned about.
Forget to shuffle, and the check alone isn't enough to make it interesting. Run the
identical algorithm — real find/union calls, a real cycle check — but skip
the Fisher–Yates step and process the 60 candidate walls in the order they're generated (row by row,
east walls before south walls). It's still a perfectly valid spanning tree: exactly 35 removed, 25
standing, every room still reachable from every other by exactly one path — the cycle check alone
already guarantees that much, order or no order. But it's a degenerate maze: one raster-order run on
this page's own 6×6 grid produced only 4 branch points (rooms with three or more open sides) and 6
dead ends, against an average of 8.39 branch points and 11.40 dead ends measured across 2,000 randomly
shuffled runs of the same grid. The cycle check is what makes the result correct; only the shuffle
step is what makes it worth calling a maze.
Time: O(E α(E)), where E is the number of candidate
walls (R·(C−1) + C·(R−1) for an R×C grid — 60 for this page's 6×6 demo) — a
Fisher–Yates shuffle over the wall list, plus one find/union pair per wall,
the same near-constant-per-operation bound as plain Union-Find itself. Space:
O(R·C) for the parent and rank arrays, plus O(E) to hold the shuffled wall
list.
This site's guide, Choosing a Union-Find Variant, places this entry alongside Offline Lowest Common Ancestor, Small-to-Large Merging, Kruskal's Reconstruction Tree, and Offline Dynamic Connectivity as a fifth application built on top of Union-Find rather than a sixth competing extension of it.