This site's eleventh Disjoint Set entry, and a sixth structure
built as an application on top of Union-Find — picked while rereading the category for a genuine
gap rather than by balance alone (Disjoint Set and Non-Comparison Sorts were tied at ten). Offline Lowest Common Ancestor, Small-to-Large Merging, Kruskal's Reconstruction Tree, Offline Dynamic Connectivity, and Randomized Kruskal's Maze
Generation all use Union-Find's answer to build something else, and every one of their real
engineering problems lives on the union side — which edges to process, which structure to
build on top, when to throw the answer away. Percolation is the first entry in this category where
the interesting problem is on the query side instead. A porous material — soil, rock, an
electrical network — is modeled as an n×n grid of sites, each either open or blocked;
the system percolates if some chain of open sites connects the top row to the
bottom row. The Union-Find trick that answers this in O(α(n²)) instead of a full
flood-fill per query is two virtual nodes — but naively reusing that same trick to answer a second,
subtler question ("is this specific open site connected to the top, not just the whole system to the
bottom?") produces a wrong answer with no incorrect union anywhere in sight. See Pitfalls below.
100 sites, 10 rows by 10 columns, all blocked (dark) to start. Press Step to open the next site in this run's random order: it turns tan if it's open but not yet connected to the top row, or blue if it's full — open and connected to the top row by a chain of open sites. Press Run to open sites automatically; it stops the moment the system percolates, same as Step does, because that's the one moment this simulation exists to find. Once that happens, one real chain of full sites from the top row to the bottom row gets an outlined border — a concrete witness, not just a yes/no answer. Press Reset for a fresh random order. On this page's own 10×10 grid, percolation typically arrives around the 59th opened site, not far from the theoretical site-percolation threshold for a square grid (roughly 0.5927 — measured directly below in Pitfalls).
The naive way to check "does the system percolate?" is a flood fill from every open site in the
top row, looking for one that reaches the bottom row — correct, but O(n²) per query,
paid again after every single site opens. Union-Find turns that into O(α(n²)) with two
extra elements bolted onto the structure: a virtual top node, unioned with every open site in row 0,
and a virtual bottom node, unioned with every open site in row n−1. Opening a site
unions it with any already-open neighbor (up, down, left, right) exactly the way any other Union-Find
application merges adjacent structure — and now percolates() is just one
find comparison: are the virtual top and virtual bottom node in the same group? If they
are, some chain of real unions connects them, and that chain can only run through open sites, row by
row, from top to bottom.
The subtlety is that the site-percolation problem actually has two queries, not one:
percolates() asks about the whole system, but isFull(r, c)
asks about one specific open site — is this site connected to the top, the way water
seeping down from the surface would actually reach it? That second query matters on its own (it's
what the "full" coloring above answers for every site, not just a single yes/no for the whole grid),
and it looks like the same virtual-top-node trick should answer it too: find(site) ===
find(virtualTop). It does — as long as the virtual bottom node was never involved in that
structure at all. The moment one shared Union-Find handles both queries, the virtual bottom node
becomes a second path into the same component the moment the system percolates, and every open site
merely touching row n−1 reports full whether or not it has any real path to the top.
That's exactly the pitfall below, and it's why the reference implementation keeps two separate
structures rather than one.
Matches the demo above: plain union-by-rank Union-Find (same find/union
pair every other Disjoint Set page on this site uses), instantiated twice — ufFull gets
only the virtual top node, ufPerc gets both:
function makeUF(n) {
const parent = Array.from({ length: n }, (_, i) => i);
const rank = new Array(n).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(a, b) {
const ra = find(a), rb = find(b);
if (ra === rb) return;
if (rank[ra] < rank[rb]) parent[ra] = rb;
else if (rank[ra] > rank[rb]) parent[rb] = ra;
else { parent[rb] = ra; rank[ra]++; }
}
return { find, union };
}
function makePercolationSystem(n) {
const N = n * n;
const virtTop = N, virtBottom = N + 1;
const ufPerc = makeUF(N + 2); // top + bottom — answers percolates()
const ufFull = makeUF(N + 1); // top only — answers isFull(), backwash-free
const open = new Array(N).fill(false);
const id = (r, c) => r * n + c;
const DIRS = [[-1, 0], [1, 0], [0, -1], [0, 1]];
function openSite(r, c) {
if (open[id(r, c)]) return;
open[id(r, c)] = true;
if (r === 0) { ufPerc.union(id(r, c), virtTop); ufFull.union(id(r, c), virtTop); }
if (r === n - 1) { ufPerc.union(id(r, c), virtBottom); } // NOT ufFull — the backwash fix
for (const [dr, dc] of DIRS) {
const nr = r + dr, nc = c + dc;
if (nr >= 0 && nr < n && nc >= 0 && nc < n && open[id(nr, nc)]) {
ufPerc.union(id(r, c), id(nr, nc));
ufFull.union(id(r, c), id(nr, nc));
}
}
}
function isOpen(r, c) { return open[id(r, c)]; }
function isFull(r, c) { return open[id(r, c)] && ufFull.find(id(r, c)) === ufFull.find(virtTop); }
function percolates() { return ufPerc.find(virtTop) === ufPerc.find(virtBottom); }
return { openSite, isOpen, isFull, percolates };
}Backwash: answer isFull from the same structure that answers
percolates, and open sites along the bottom row lie about being full. Drop
ufFull and answer both queries from the single structure that already has both virtual
nodes wired in. It still gets percolates() right — that query never claimed anything
about individual sites. But the instant the system percolates, the virtual bottom node sits in the
same component as the virtual top node, and any open site touching row n−1 is
already unioned with that virtual bottom node, real path to the top or not — so it reports full
regardless. Water flows the wrong way up through the "drain," which is where the name comes from.
Measured directly against this page's own two-structure reference implementation across 20,000
random 10×10 runs, checked at the exact moment each one first percolates: 15,905 of them (79.5%) had
at least one falsely-full open site at that instant, and across all runs 103,908 of 1,181,260 open-site
checks (8.80%) were wrong. The smallest hand-checkable case found: a 4×4 grid opened in the order
(2,1) (1,3) (1,2) (0,2) (2,0) (1,0) (3,3) (3,0) (1,1) percolates the moment
(1,1) opens — row 1 is entirely open and bridges row 0's (0,2) down through
row 2 to row 3's (3,0). Site (3,3) is also open by then, but its only open
neighbors are itself — no path to (1,1)'s component at all. The single-structure version
reports it full anyway, purely because it touches the virtual bottom node that's now connected to the
virtual top; the two-structure version above correctly says no.
Use 8-directional (diagonal) adjacency instead of 4-directional, and the whole system percolates at a different density — not a small rounding difference, a different physical answer. This isn't a bug in the Union-Find bookkeeping; both versions correctly answer "does this adjacency graph connect top to bottom." It's a modeling error: real site percolation on a square lattice is defined over 4-directional (von Neumann) neighbors, and switching to 8-directional (Moore) neighbors — letting diagonal contact count as connected — makes percolation dramatically easier, since a diagonal-only chain that plain 4-adjacency would call two separate components now counts as one. Measured by running this page's own simulation to find each run's opened-fraction at first percolation, averaged over 1,000 trials on an 80×80 grid (large enough that the average settles down close to the known constant rather than bouncing around on a small grid): 4-directional adjacency percolates at an average of 59.21% of sites open, matching the commonly cited literature estimate for this exact model (≈59.27%); 8-directional adjacency percolates at 40.75% (literature ≈40.73%) — sites need to fill barely two-fifths of the grid, not three-fifths, before the material as a whole "conducts." Both numbers are internally consistent and both queries return correct answers for their own graph — the pitfall is picking the wrong graph for the physical question being asked.
Time: O(α(n²)) amortized per openSite call (at most
four neighbor unions plus, on the top or bottom row, one virtual-node union) and
O(α(n²)) per isFull or percolates query — both are a fixed
number of find calls, not a scan of any row. The naive alternative — flood-fill from the
top row on every query, or compare every top-row root against every bottom-row root — answers
correctly too, just at O(n²) per query instead of near-constant, paid again after every
single site opens. Space: O(n²) for the open-site array and both
Union-Find structures' parent/rank arrays (n² + 1 elements for ufFull,
n² + 2 for ufPerc) — twice the parent/rank storage of a single structure,
the direct cost of keeping the backwash fix.
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, Offline Dynamic Connectivity, and Randomized Kruskal's Maze Generation as a sixth application built on top of Union-Find rather than a seventh competing extension of it.