Metadata on the Roots

Plain DSU answers a yes/no question. Almost no problem stops there - they ask how many groups, how big is the biggest, what is the smallest label in this group. All of those are answerable for free, because a merge already touches exactly the two values that need combining.

This page is the pattern for hanging any such value on the structure, and the one rule that keeps it correct.

1. count: how many groups are left

One scalar, two lines, and it answers the single most-asked DSU question.

self.count = n # in __init__: everything is its own group

...

self.count -= 1 # in union, INSIDE the "roots differ" branch

Start at n, decrement once per successful merge. After feeding every edge of an undirected graph, count is its number of connected components - without a traversal, without an adjacency list, and without ever materialising the graph.

count tracks the number of roots. It never goes up.

⚠

Decrement inside the branch, not after it

count -= 1 belongs inside the if roots differ branch. Put it after the if and every repeated or duplicated edge silently steals a component. The symptom is a component count that is too low by exactly the number of duplicate edges in the input - which is zero on the samples and nonzero on the real test.

Two derived facts you get from count alone, both of which show up as whole problems:

• Edges needed to connect everything: count - 1. If a network has k components, exactly k - 1 cables join them into one.
• Is it one big group? count == 1. Combined with len(edges) == n - 1, that is the complete "is this a valid tree" test.

2. size: how big is this group

Each element starts at size = 1. On merge, the winning root absorbs the loser's total:

self.size[winner] += self.size[loser]

The loser's entry is left alone - stale, unread, harmless. That is the whole mechanism, and it is why size is only meaningful at a root.

After the merge, size[1] still says 2. It is not wrong so much as no longer anybody's business.

The safe accessor, and the only form you should ever write:

def getSize(self, a):

return self.size[self.find(a)]

⚠

size[x] without find is the classic silent wrong answer

A bare size[x] returns the size of whatever group x last led. For a node that was never a root it returns 1; for a node that was absorbed it returns its size at absorption time. Both are plausible numbers, which is why this fails a large test and not a small one. Never index size with anything but a find result.

Two problems fall straight out:

• Largest component: max(size[i] for i in range(n) if parent[i] == i), or just track a running best = max(best, size[winner]) inside union and read it in O(1).
• "How many people in the same group as x": getSize(x).

3. The rule: any mergeable value can ride along

count and size are two instances of one pattern. If a per-group value can be computed from the two groups' values when they merge, and never needs recomputing otherwise, it can live on the root for free.

The requirement is exactly that the combine operation is associative and has an identity - a monoid, if you want the word. + for size, min, max, or, and, gcd all qualify. average does not, but (sum, count) does, and you divide at the end.

# in __init__

self.best = list(range(n)) # or values[:], or [0] * n, ...

 

# in union, next to the size update

self.best[winner] = min(self.best[winner], self.best[loser])

Carry	Combine on merge
	What it answers
size	size[w] += size[l]
	largest component, "how many like me"
min_label	min_label[w] = min(min_label[w], min_label[l])
	Accounts Merge (smallest email), lexicographically smallest representative
max_value / sum	max / +
	richest group, total weight of a component
edge_count	e[w] += e[l] + 1 on merge, e[root] += 1 when union returns False
	"is this component a tree" (e == size - 1) versus "does it have a cycle"
sorted_members	does not qualify - concatenation is fine but the list itself is O(n) to carry
	Do this in one O(n) bucketing pass at the end instead - see section 5.

Mnemonic

If you can answer it for the merged group knowing only the two answers, put it on the root. If you need the members to answer it, you cannot - collect them at the end instead. That single test decides every "can DSU do this" question about metadata.

4. Deciding the winner: rank, size, or the value itself

Union by rank and union by size both pick a winner for performance. But some problems need a specific winner for correctness - "the representative must be the lexicographically smallest email," "the root must be the node with the highest score."

You cannot have both. Forcing the winner destroys the balance guarantee and find degrades toward O(log n) or worse.

Situation	What to do
	Why
You just need to report a specific element per group	Keep union by rank/size, and carry the wanted element as metadata (min_label above).
	Balance is preserved and the answer is exact. This covers almost every case, including Accounts Merge.
The representative itself must be a specific element	Force the winner, and accept the slower find.
	Rare, and usually a sign the problem wanted the metadata form. With path compression still on, the practical cost is small.
You need a stable group id across time	Do not use the root. Assign ids in a final O(n) pass.
	Roots change identity on every merge; anything you cached is invalidated silently.

5. Getting the groups out at the end

DSU has no member lists. One pass builds them:

from collections import defaultdict

 

groups = defaultdict(list)

for i in range(n):

groups[dsu.find(i)].append(i) # find, not parent

O(n) once, and the result is a dict from representative to member list. Do this after all unions, never inside the loop.

⚠

Bucket by find(i), not by parent[i]

parent[i] is one hop up, not the root. Bucketing by it splits a component into as many groups as it has distinct parents - and on a fully-compressed forest the two happen to agree, so this bug appears only after a merge sequence that left some node at depth 2. Always call find.

Two things this pass gives you at once, and both are common final answers:

• The groups themselves, in groups.values().
• A dense relabelling: enumerate(groups) maps each representative to 0, 1, 2, ..., which is what a problem wants when it asks you to "return the component id of each node."

Next: Recognising the Pattern - the phrases that mean DSU, how to encode non-integer elements, and the tricks that turn a problem that does not look like connectivity into one that is.