Variants

Basic DSU answers one question: are these two in the same group? Three variants answer strictly more, and all three keep the same find/union shape - they just carry extra data along the parent pointers and update it during path compression.

Read this page once you are comfortable with Find & Union. Every variant here is the reference implementation with one field added.

1. The map

Variant	Extra state per element
Variant	Answers
Plain DSU	nothing
Plain DSU	"same group?"
Parity DSU	one bit: parity of the path to the root
Parity DSU	"same side or opposite sides?" - bipartiteness, enemies, alternating constraints
Weighted DSU	a number: value relative to the root
Weighted DSU	"what is `a/b`?" or "how much taller is `a` than `b`?"
Rollback DSU	a history stack of merges
Rollback DSU	"undo the last union" - at the cost of path compression

The first two are the same construction with a different group operation: XOR for parity, multiply (or add) for weights. If you understand one you understand both.

Each element stores its own value RELATIVE to its root. The root's absolute value is never known and never needed.

2. Parity DSU: "same group" vs "opposite groups"

Sometimes the relation is not "these two are together" but "these two are on opposite sides" - enemies who must be split, values that must differ. Store one extra bit per element: the parity of the path from it up to its root. Two elements are then on the same side exactly when their parities to a shared root match, and a contradiction is an odd cycle - which is exactly non-bipartiteness.

class ParityDSU:
    def __init__(self, n):
        self.parent = list(range(n))
        self.parity = [0] * n            # parity of the path from i up to its root
 
    def find(self, x):
        if self.parent[x] == x:
            return x
        root = self.find(self.parent[x])
        # read the parent's parity AFTER the recursion fixed it, BEFORE rewiring
        self.parity[x] ^= self.parity[self.parent[x]]
        self.parent[x] = root
        return root
 
    def union(self, a, b, differ=1):
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            # already related: is the existing relation consistent with this one?
            return (self.parity[a] ^ self.parity[b]) == differ
        self.parent[rb] = ra
        self.parity[rb] = self.parity[a] ^ self.parity[b] ^ differ
        return True

Parity's find steps must run in this exact order

The two lines inside find are order-dependent and both must sit between the recursion and the rewiring. self.parity[self.parent[x]] is only the parent-to-root parity after the recursive call has compressed it, and it is only readable before self.parent[x] is reassigned to the root. Swap the two statements and the parity silently becomes garbage while connectivity stays correct - so find still works, the groups are still right, and only the same-side answers are wrong.

Mnemonic

Parity DSU is bipartite checking without a traversal. The 2-coloring BFS needs the whole graph up front; parity DSU accepts edges one at a time and reports the first one that closes an odd cycle. Use the BFS when the graph is given, and this when the edges stream in.

The cheap alternative, when you would rather not modify find at all, is the 2n trick from Recognising the Pattern: allocate 2n elements, read i + n as "not i", and union (a, b+n) and (b, a+n) per conflict. Same answers, unmodified DSU, twice the memory.

3. Weighted DSU: ratios and offsets

Replace the parity bit with a number and XOR with multiplication, and the same machinery propagates ratios: store weight[x] = value(x) / value(parent[x]). This is what "evaluate division" style problems are - a/b = 2, b/c = 3, what is a/c? Connectivity says whether the question is answerable at all, and the weights give the answer.

class RatioDSU:
    def __init__(self):
        self.parent = {}
        self.weight = {}                 # weight[x] = value(x) / value(parent[x])
 
    def find(self, x):
        if x not in self.parent:
            self.parent[x] = x
            self.weight[x] = 1.0
        if self.parent[x] == x:
            return x
        root = self.find(self.parent[x])
        self.weight[x] *= self.weight[self.parent[x]]     # same ordering rule
        self.parent[x] = root
        return root
 
    def union(self, a, b, ratio):         # asserts a / b == ratio
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return                        # already related; could verify consistency here
        self.parent[rb] = ra
        self.weight[rb] = self.weight[a] / (ratio * self.weight[b])
 
    def query(self, a, b):
        if a not in self.parent or b not in self.parent:
            return -1.0                   # never mentioned: unanswerable
        if self.find(a) != self.find(b):
            return -1.0                   # unrelated: unanswerable
        return self.weight[a] / self.weight[b]

Every element stores its value relative to its root, so the root's own value cancels out.

weight[a] / weight[b] is (a/root) / (b/root) = a/b - the unknown root value divides away. That is why the structure never needs to know any absolute value, and why "unrelated" is genuinely unanswerable rather than merely unknown.

Additive and multiplicative weighted DSU can't mix

Use the same trick with + instead of * for offsets, and never mix the two. "A is 5 taller than B" is additive DSU (weight[x] = value(x) - value(parent[x]), combined with +=), and ratios are multiplicative. The code is identical apart from the operator and the identity element (0 vs 1.0) - initialising a multiplicative DSU's weights to 0 makes every query return zero, with no error anywhere.

4. Rollback DSU: undoing a union

Plain DSU cannot split a group - path compression destroys the history. Give it up, keep union by size only, and record what each union changed; then a union becomes undoable in O(1). find degrades to O(log n), which is the price of the undo.

class RollbackDSU:
    def __init__(self, n):
        self.parent = list(range(n))
        self.size = [1] * n
        self.history = []                # (child_root, parent_root) per real merge
 
    def find(self, x):                   # NO path compression: history must stay valid
        while self.parent[x] != x:
            x = self.parent[x]
        return x
 
    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            self.history.append(None)    # record the no-op so rollback counts match
            return False
        if self.size[ra] < self.size[rb]:
            ra, rb = rb, ra
        self.parent[rb] = ra
        self.size[ra] += self.size[rb]
        self.history.append((rb, ra))
        return True
 
    def rollback(self):
        entry = self.history.pop()
        if entry is None:
            return
        child, root = entry
        self.size[root] -= self.size[child]
        self.parent[child] = child       # detach: exactly undoes the one write

Rollback DSU can't use path compression

Rollback and path compression are mutually exclusive. Compression rewires nodes that the history never recorded, so undoing the recorded merge leaves those nodes pointing into the wrong tree. If you need undo, you give up compression - there is no version that keeps both.

Mnemonic

DSU can merge but never split, so when a problem deletes edges, run time backwards. "What is the last day the network is still connected" or "after each removal, how many components" become ordinary unions if you process the events in reverse order and reverse the answers at the end. That trick avoids rollback entirely, and it is usually the intended solution.

Rollback exists for the case reversal cannot cover: queries that must be answered online, or a divide-and-conquer over time (the "offline dynamic connectivity" technique) where you add a batch of edges, recurse, and undo the batch on the way out. If a problem is not one of those two, reverse time instead.

5. Choosing between them

The problem says	Reach for
The problem says	Why
"these two must be in different groups"	parity DSU, or the 2n trick
"these two must be in different groups"	A contradiction is an odd cycle. Plain DSU cannot represent "apart".
"a is twice b", "a is 5 more than b", then a query about two others	weighted DSU (multiplicative or additive)
	The chain of relations composes along the parent pointers.
"after removing edge k, how many components" and all removals are known	plain DSU, backwards
	Cheapest by far. No variant needed.
the same, but each query depends on the previous answer	rollback DSU
the same, but each query depends on the previous answer	You cannot reverse an online sequence, so you must be able to undo.
"can a reach b" on a directed graph	none of these - use SCC
"can a reach b" on a directed graph	No DSU variant handles asymmetry; union is symmetric by construction.

Every variant costs you the plain DSU's simplicity

Do not reach for a variant until plain DSU has actually failed. Parity, weights and rollback each add a field that has to be maintained in find, union and through compression, and every one of them fails silently when mis-ordered. If the 2n trick or reverse-time covers your case, take it - the code you do not write cannot be subtly wrong.

Back to the section index for the practice problems, or to Recognising the Pattern if you are still deciding whether DSU is the right tool at all.

1. The map​

2. Parity DSU: "same group" vs "opposite groups"​

3. Weighted DSU: ratios and offsets​

4. Rollback DSU: undoing a union​

5. Choosing between them​

1. The map

2. Parity DSU: "same group" vs "opposite groups"

3. Weighted DSU: ratios and offsets

4. Rollback DSU: undoing a union

5. Choosing between them