Union-Find answers one question fast: "are x
and y in the same group?" Weighted Union-Find (also called Union-Find with
potentials) answers a sharper one: "given everything I've been told, what's the known numeric difference
between x and y?" Every union now carries a weight — not just "these two are
related," but "y is exactly w more than x." That single addition
also buys something plain Union-Find can't offer at all: if a new constraint contradicts what earlier
unions already imply, the structure catches it, in the same near-constant time as everything else. This
is the standard trick behind checking a system of relative constraints for consistency — "B is 5 more
than A," "C is 2 less than B," does that ever imply something impossible? — without re-deriving every
value from scratch on each new fact.
Same eight elements as Union-Find, 0
through 7, but every union now also carries a weight. Click a node to select it as
A (dashed border), click a second to select it as B (solid border), set
the weight field, then press Union to record "B = A + weight." Press Find
on a single selected node to see its offset from its set's root — the number under each non-root node is
that live offset. If you union two elements already in the same set, the demo checks the weight against
what's already implied: consistent, and it's a no-op; contradictory, and it's rejected and flagged in red
instead of silently applied.
Give every element x a hidden, never-fully-known value value(x). Nothing in
the structure ever learns any single element's absolute value — only differences between values,
supplied one union at a time. Alongside the usual parent pointer, each non-root element
x stores a potential: value(x) - value(parent(x)), its offset
from its own parent. find(x) walks up to the root exactly as before, but now sums potentials
along the way, so it returns both the root and value(x) - value(root) — the offset
from x all the way to its set's representative.
Union. union(x, y, w) means "value(y) - value(x) = w."
Find both roots first. If they're already the same root, the union adds no new information — check
whether the two elements' already-known offsets agree with w; if they don't, that's a
genuine contradiction between constraints, not a bug, and it's rejected. If the roots differ, attach one
under the other (by rank, exactly as plain Union-Find does) and give the attached root a potential that
makes the whole merged tree consistent. Working out that potential is direct algebra: if root
rx attaches under root ry, then potential(rx) = value(rx) - value(ry),
and substituting value(x) = value(rx) + offset(x) and the known relation
value(y) - value(x) = w gives potential(rx) = offset(y) - offset(x) - w. Attach
the other way and the same substitution gives the mirror-image formula with the sign flipped.
Worked example. Start empty, then union(0, 1, 3) — "value(1) = value(0) + 3" — and
union(1, 2, 2) — "value(2) = value(1) + 2." Nothing states value(2) relative to value(0) directly, but the
structure already implies it: find(2) returns offset +5 from root 0
(3 + 2), with no extra bookkeeping. A third union(0, 2, 5) is then consistent with what's
already known (implied offset is also 5) and is a no-op; union(0, 2, 6) instead contradicts it — the
structure already knows the answer is 5, not 6 — and is rejected. That check costs exactly two
find calls, the same near-constant operation as everything else here.
Matches the demo above. The important line is the one a first draft is most likely to skip: path compression has to rewrite both the pointer and the potential, together, or the shortcut it just took silently stops meaning what its stored number says it means (see Pitfalls):
class WeightedDisjointSet {
#parent;
#potential;
#rank;
constructor(n) {
this.#parent = Array.from({ length: n }, (_, i) => i);
this.#potential = new Array(n).fill(0);
this.#rank = new Array(n).fill(0);
}
// returns { root, offset } where offset === value(x) - value(root)
find(x) {
if (this.#parent[x] === x) return { root: x, offset: 0 };
const { root, offset } = this.find(this.#parent[x]);
const total = this.#potential[x] + offset;
this.#parent[x] = root; // path compression: repoint...
this.#potential[x] = total; // ...and re-express the offset relative to the NEW parent (the root)
return { root, offset: total };
}
// records "value(y) - value(x) === w"; returns false if that contradicts what's already known
union(x, y, w) {
const a = this.find(x), b = this.find(y);
if (a.root === b.root) return (b.offset - a.offset) === w;
let small, big, pot;
if (this.#rank[a.root] < this.#rank[b.root]) {
small = a.root; big = b.root; pot = b.offset - a.offset - w;
} else if (this.#rank[a.root] > this.#rank[b.root]) {
small = b.root; big = a.root; pot = w + a.offset - b.offset;
} else {
small = b.root; big = a.root; this.#rank[a.root]++; pot = w + a.offset - b.offset;
}
this.#parent[small] = big;
this.#potential[small] = pot;
return true;
}
// value(y) - value(x), or null if x and y aren't known to be related at all
diff(x, y) {
const a = this.find(x), b = this.find(y);
return a.root === b.root ? b.offset - a.offset : null;
}
}Path compression must carry the offset, not just the pointer — verified with real numbers, not
just argued. Build an 8-element tree via seven weighted unions so that node 7 sits
three hops from root 0 (parent chain 7 → 6 → 4 → 0, potentials
+4, -3, +7 respectively). The correct offset for node 7 is
+8 relative to root 0, and a correct implementation returns 8 from
find(7) every time it's called, including a second call right after the first. A buggy variant
that repoints parent[7] straight to the root during compression but forgets to rewrite
potential[7] to match — leaving it at its old value, still relative to the node it used to
point at, not the root — returns the correct 8 on the first call (it still walks the
real chain that time) but 4 on the very next call: the shortcut is now in place, so the second
call trusts the stale local potential directly instead of re-deriving it, and 4 was never the
right answer for anything. No crash, no exception, no visible sign anything is wrong — just a wrong number
that looks exactly as confident as a right one. Run both implementations back to back and this is exactly
what happens; it isn't a hypothetical.
Rejecting a contradiction doesn't tell you which constraint was wrong. Same limit as
plain Union-Find's "merging is one-way" — there's no way to retract an earlier union that turns out, in
hindsight, to have been the bad one. A rejected union just means "this new fact conflicts with something
already accepted"; deciding which of the two conflicting facts to keep is a judgment call outside the
structure, not something union can resolve for you.
"Not yet related" isn't "consistent." Contradiction detection only fires between
elements the union history actually connects, directly or transitively. Two elements in components that
have never been unioned have no stored relationship at all — diff(x, y) returns
null, not 0 and not an error. That's not a gap in the implementation; there is
genuinely no information to check yet.
Weights and rollback are separate extensions, not stackable for free. This page trades plain Union-Find's near-constant time for the ability to track differences; Union-Find with Rollback trades it instead for the ability to undo the most recent merge, and it can only do that by giving up path compression — which is exactly the mechanism this page's own potentials ride along during. Combining both ideas in one structure is possible in principle but isn't free: it needs care neither page's implementation provides on its own.
Time: identical to plain Union-Find — O(α(n)) amortized per
find or union with both union-by-rank and path compression, since tracking a
potential alongside the pointer is O(1) extra work per node touched, changing nothing about
the amortized bound. The first Pitfall above is entirely about correctness, not performance — a
build that forgets to update potentials runs at exactly the same speed as one that doesn't, and gives wrong
answers just as fast. Space: O(n) — one extra number per element beyond
plain Union-Find's parent and rank arrays.
This site's guide, Choosing a Union-Find Variant, compares this entry against the other three Disjoint Set structures that extend the same core contract side by side.