Graphs IV — Union-Find (DSU)

Review boundary and corrected contracts

Union by rank/size plus path compression gives the inverse-Ackermann amortized bound. With rank alone the height is logarithmic, not linear. Path compression alone is not the combined proof. Basic DSU supports additions, not arbitrary deletions; rollback is a separate design.

The examples below teach the stated input contracts; fragments and deliberately incorrect counterexamples are exercises, not production implementations. Complexity counts elementary operations unless a bit-cost or allocation caveat is stated. Practice times are suggestions, not measured performance or hiring guarantees.

Learning objective: Memorise DSU cold — find with path compression, union by rank, component counter — and recognise the incremental-connectivity problems where it beats DFS outright.

Series: LeetCode — From Basics to Production-Ready · Session 30 / 65 · Phase 1 · Core patterns

Why this session exists

Union-find is the highest ratio of power to lines in the entire design review canon. Fifteen lines, near-constant amortised time, and it trivialises a whole family of problems that are awkward with DFS: incremental connectivity, redundant edges, account merging, Kruskal's MST, and every "are these two things in the same group" query.

The reason it deserves its own session rather than a footnote in the graph chapter is that it answers a different question. DFS answers connectivity for a graph you already have. DSU answers connectivity for a graph that is being built one edge at a time, and it answers each query as the edges arrive. Re-running DFS after every edge insertion is O(E·(V+E)). DSU costs O(V + E·α(V)), including initialization. Here α is inverse Ackermann, which grows so slowly that it is treated as a tiny factor for practical inputs.

Memorise it. This is one of maybe four things in this series I would tell you to learn as literal muscle memory, while keeping its contract explicit: valid indices, equivalence classes, additions, and no arbitrary splitting.

Blank-file warm-up

Five minutes, empty file, no notes. Write from memory:

find(x)      — with path compression
union(a, b)  — by rank, returns False if already joined

The two things that go wrong. First, writing find without compression and without balancing — both omitted can permit O(n) calls. Second, forgetting the if ra == rb: return False guard, which is what lets union double as a cycle detector and as the component counter's trigger.

If you cannot produce both in five minutes today, this is the session to repeat until you can.

Pattern anatomy

The shape of problem that summons DSU: a stream of "these two things are now related" facts, plus questions about grouping or about whether a fact was redundant. The relation must be an equivalence — reflexive, symmetric, transitive. Connectivity, "same account", or equality classes qualify. Direct friendship is not transitive; DSU would compute friendship-connected groups, not whether two people are directly friends. If the relation is directional, DSU does not apply; that is a directed-graph problem.

The invariant: every element points, directly or transitively, at a single canonical representative for its set, and two elements are in the same set if and only if they resolve to the same representative. Path compression flattens the pointer chains without changing which representative anything resolves to, which is why it is always safe.

The template. This is the version to memorise:

class DSU:
    def __init__(self, n):
        self.parent = list(range(n))     # every node is its own root
        self.rank = [0] * n              # upper bound on tree height
        self.count = n                   # number of disjoint components
 
    def find(self, x):
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]   # path halving
            x = self.parent[x]
        return x
 
    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False                 # already joined: this edge is redundant
        if self.rank[ra] < self.rank[rb]:
            ra, rb = rb, ra              # attach the lower-rank root under the higher-rank root
        self.parent[rb] = ra
        if self.rank[ra] == self.rank[rb]:
            self.rank[ra] += 1           # rank bound grows only on a tie
        self.count -= 1
        return True

Four details that carry the whole thing.

self.parent[x] = self.parent[self.parent[x]] is path halving — each node on the walk is re-pointed at its grandparent. It is iterative, so no recursion limit, and it gives the same asymptotic guarantee as full path compression while being shorter than the two-pass recursive version.

Union by rank (or maintained size). Rank is a historical upper bound on height, not the current height after compression. It increments on equal-rank merges. A maintained component-size counter is an equally valid balancing heuristic; do not repeatedly scan subtrees to compute sizes. Omitting balancing permits a linear-height tree and a linear-cost individual find, even if later finds compress it.

return False on an already-joined pair. This single line is a cycle detector for undirected graphs and is the entire solution to Redundant Connection.

self.count starts at n and decrements on every successful union. That gives you the number of connected components in O(1) at any moment, without a second pass.

The functional form, when you do not want a class:

parent = list(range(n))
 
def find(x):
    while parent[x] != x:
        parent[x] = parent[parent[x]]
        x = parent[x]
    return x
 
def union(a, b):
    ra, rb = find(a), find(b)
    if ra == rb:
        return False
    parent[rb] = ra
    return True

This fragment requires n to be defined first and valid indices in [0,n). It omits both the rank array and the component counter, not just class syntax. Compression alone has a weaker amortised O(log n) bound; an individual find can still be linear. State the tradeoff rather than transferring the combined inverse-Ackermann guarantee to this version.

The cue

You are looking at a union-find problem when the statement contains one of these tells:

1. Edges arrive as a stream and you are asked about connectivity as you go. Redundant Connection, Number of Operations to Make Network Connected. DFS would have to re-run from scratch after each edge.
2. "Are these two in the same group" asked many times. Each query must be O(1)-ish, and DSU is a compact standard structure for insert-only merging; it is not the only possible connectivity structure.
3. Merging entities by shared attributes. Accounts Merge (shared email), Similar String Groups. The attribute is the bridge; you union everything sharing it.
4. "Count connected components" on a static graph. DSU works and DFS works — pick either, but DSU is fewer lines and reads more directly.
5. Detecting a cycle in an undirected graph. The union returning False is the detection. Note this is undirected only; directed cycles need the three-colour DFS from session 29.
6. Minimum spanning tree. Kruskal's is: sort edges by weight, union them in order, skip the ones that return False. DSU is the entire supporting structure.

The negative cue: DSU cannot un-merge. If the problem involves removing edges or splitting groups, DSU is the wrong tool — offline deletion-only histories can be reversed after initializing the final remaining graph. Mixed insertions/deletions or online splitting require a different design, such as rollback with an offline time decomposition.

Guided solve

Number of Connected Components in an Undirected Graph. Given n nodes labelled 0 to n−1 and a list of undirected edges, return the number of connected components.

Name the structure first. Every node starts in its own component, so the count starts at n. Every edge that joins two different components reduces the count by one. Every edge that joins two nodes already in the same component changes nothing — it is a redundant edge inside an existing component.

That is the whole solution stated in English, and the code is a direct transcription.

def countComponents(n, edges):
    parent = list(range(n))
    rank = [0] * n
    count = n
 
    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x
 
    for a, b in edges:
        ra, rb = find(a), find(b)
        if ra == rb:
            continue                     # same component already: no change
        if rank[ra] < rank[rb]:
            ra, rb = rb, ra
        parent[rb] = ra
        if rank[ra] == rank[rb]:
            rank[ra] += 1
        count -= 1
 
    return count

Trace on n = 5, edges = [[0,1],[1,2],[3,4]]. Start count 5. Edge (0,1): different roots, merge, count 4. Edge (1,2): find(1) resolves to 0, find(2) is 2, different, merge, count 3. Edge (3,4): different, merge, count 2. Answer 2 — the components are \{0,1,2\} and \{3,4\}.

Now the part worth saying aloud under a tight review. The DFS solution to this problem is equally correct and roughly the same length. So why choose DSU? Because of the follow-up. "Now the edges arrive one at a time and after each one I want the current component count." DSU answers that in O(α) per edge with no code change at all. DFS has to re-traverse the whole graph after each edge, which is O(E·(V+E)) total. Volunteering that follow-up before a reviewer asks it is worth more than the solution itself.

Kruskal's minimum spanning tree is four lines on top of the DSU you just wrote: sort the edges by weight ascending, iterate, call union(u, v), and keep the edge if it returns True. Stop when you have kept n−1 edges. The return False case is exactly "this edge would create a cycle", which is exactly the edge Kruskal must reject. For a disconnected graph, fewer than n−1 edges are accepted: the result is a minimum spanning forest, not an MST. The cut/exchange argument, not DSU alone, proves the greedy weight choice, and sorting costs O(E log E).

Solo timed

Fifteen minutes each, timer visible, no editorial until it fires.

• Redundant Connection — return the edge that, when removed, leaves a tree. Think about what union returning False tells you and why processing edges in input order gives the last such edge, which is what the problem asks for.
• Accounts Merge — the nodes are not given as integers. Before writing any DSU, decide what you are unioning: account indices, or emails? Both work; one is noticeably cleaner. Pick one and commit.

If both land early, do Number of Operations to Make Network Connected. It needs two facts from the DSU: the component count, and how many edges were redundant. Both are already available in the template.

Common failure modes

Linking arbitrary nodes instead of roots inside union. Writing parent[b] = a can move only b’s subtree and split a previously connected component; if a is beneath b it can even create a parent-pointer cycle. This is the single most damaging DSU bug and it produces wrong answers silently.

Omitting path compression. With union by rank retained, height remains O(log n). If both balancing and compression are absent, an adversarial chain permits O(n) find. The inverse-Ackermann amortized bound needs both heuristics.

Decrementing the component count unconditionally. The decrement belongs after the ra == rb guard. Decrementing on every edge gives n - len(edges), which can go negative.

Comparing parent[a] == parent[b] to test same-set. Two nodes in the same set can have different immediate parents; only their roots match. Always compare find(a) == find(b).

Passing strings to this array-backed template. Map emails or other entities to dense indices before using it. A different DSU can store parents in a dictionary keyed directly by hashable entities; indexing is a contract of this implementation, not an inherent DSU requirement.

Using DSU for a directed graph. Union-find models an undirected equivalence relation. Applying it to directed edges loses the direction entirely, so Course Schedule cannot be solved this way — a valid DAG with a diamond looks identical to a cycle.

Myth: Path compression and union by rank are optional micro-optimisations — the plain version is the same algorithm with a slightly worse constant.

Why: The heuristics change asymptotic costs without changing the partition answer. Under the displayed parent[rb] = ra orientation, (0,1), (0,2), (0,3) builds a star, not a chain. With both heuristics omitted, (1,0), (2,1), (3,2), … makes each new singleton the root and creates a chain. Repeated finds at the old bottom then cost linear time each. Keeping compression shortens later walks; keeping rank alone bounds height logarithmically; combining them gives the inverse-Ackermann amortised bound.

Steps 1: Because 'connected to' is an equivalence relation, the nodes partition into disjoint sets, and each set can be named by any one of its members.

Steps 2: Because naming a set by a designated root reduces 'same set?' to 'same root?', the query becomes a pointer walk rather than a graph traversal.

Steps 3: Because compression moves parent pointers toward the same root, it preserves the represented partition and never increases those path lengths. Already-short paths may be unchanged; the iterative code uses path halving, not full flattening.

Steps 4: A root of rank r represents at least 2^r elements: rank increases only when merging two roots of the same rank. Thus rank is at most floor(log₂ n). Attaching lower rank beneath higher rank bounds height before compression, which can only shorten paths.

Steps 5: Together balancing and compression give O(α(n)) amortised time. This is a bound over a sequence, not a claim that every individual operation has constant worst-case time.

Steps 6: For a deterministic comparison, build the chain (1,0), (2,1), …, (n−1,n−2) without either heuristic and then query find(0) n times. Those queries take n(n−1) parent-edge steps. Halving or rank changes that work; this is an operation-count prediction, not a wall-clock benchmark on random unions.

Picture: Each group is a club with one president. To find out if two people are in the same club, you ask each of them who their boss is, then that boss's boss, until you reach a president. Full path compression makes every visited member report directly to the president; the displayed halving version skips a generation on each step and shortens the chain without necessarily flattening every node in one call.

Trigger: Fires when relationships arrive incrementally and you need grouping or same-group queries as they arrive — merging, connecting, joining, or detecting a redundant link.

Name: Union-Find (DSU)

Gain: O(α) amortised per operation; handles edges arriving as a stream; component count maintained for free; cycle detection is one return value; the base of Kruskal's MST

Cost: Cannot un-merge or delete edges; gives no path information — you learn that two nodes are connected but not how; useless on directed graphs

Name: DFS / BFS traversal

Gain: Gives the actual path and the members of each component; works on directed graphs; no extra structure to memorise

Cost: Must re-run from scratch after every edge insertion, which is O(V+E) per query on a mutating graph

Pick: DSU when edges arrive incrementally, when you need repeated same-group queries, or when the answer is a count or a redundant-edge identification. Traversal when you need the actual path, the explicit member list of a component, or when the graph is directed.

Complexity

Time: O(V + E · α(V)) including initialization and E operations, where α is the inverse Ackermann function. This is the classic Tarjan bound for path compression combined with union by rank. Because α(n) ≤ 4 for every practically representable n, each operation is treated as effectively constant, and the total is described as near-linear.

The bound is amortised, not worst-case per operation. With rank retained, a single find can still walk O(log V) levels; the guarantee is that the total across all operations is bounded, because each walk flattens the structure and pays for future calls.

With path compression only: amortised O(log n) per operation. With union by rank only: worst-case O(log n) per operation. With neither: O(n) worst case, and a deliberately ordered input makes it quadratic overall.

Space: O(V). Two arrays of length V — parent and rank — plus O(1) for the counter. If entities are strings, add O(V) for the entity-to-index dict. Note that the iterative find uses no stack, which is a real advantage over the recursive form on large inputs.

Self-check (answer follows each question).

Q: Inside union, why must you write parent[find(b)] = find(a) rather than parent[b] = a?

A: Only roots may be re-pointed. Re-pointing a non-root node breaks the tree: whatever hung beneath b's actual root stays attached to that root, so the two sets do not actually merge and later finds give wrong answers.

Q: What does union(a, b) returning False tell you, and which problem does that single fact solve?

A: a and b were already in the same component, so this edge is redundant and closes a cycle in an undirected graph. That is the complete solution to Redundant Connection.

Q: Why is rank incremented only when the two roots have equal rank?

A: Rank is an upper bound rather than current height after compression. Attaching a root of smaller rank under a larger one preserves that upper bound; equal ranks require increasing it by one. The size-doubling argument bounds rank by floor(log₂ n).

Q: How do you maintain the number of connected components without a second pass?

A: Initialise a counter to n and decrement it inside union, after the same-root guard. Every successful merge reduces the number of disjoint sets by exactly one.

Q: Why can DSU not be used to solve Course Schedule?

A: Union-find models an undirected equivalence relation and discards edge direction. A directed acyclic diamond and a directed cycle produce identical DSU states, so it cannot distinguish feasible from infeasible orderings.

Q: You need to answer connectivity queries on a graph where edges are being DELETED over time. Why does DSU fail, and what is the standard workaround?

A: A partition alone does not record which remaining graph edges still connect the set; even DSU without compression cannot undo arbitrary graph deletions. For a known deletion-only history, initialize DSU with edges remaining at the end, process deletions backward as insertions, and reverse query answers. Mixed updates require more machinery; simply reversing them also turns insertions into unsupported deletions.

Stretch: true

Spaced queue

Re-solve whatever is due before starting anything new today. Status ladder:

• cold — solved unaided, first attempt clean → next review in 60 days
• warm — solved but slowly or with a stumble → 21 days
• hint — needed a nudge to get started → 7 days
• failed — could not produce a working solution → 2 days, then 7 days

DSU is the one template in this series I would put on a shorter cycle than the ladder suggests. Even if today's blank-file attempt was clean, re-write find and union from memory once a week until it is genuinely automatic. It costs ninety seconds and it is the highest-return ninety seconds in the whole graph section.

• Fifteen lines, near-constant amortised time. Memorise find with path halving and union by rank as literal muscle memory.

• union returning False means the edge was redundant — that is a complete undirected cycle detector at zero extra cost.

• Initialise a counter to n and decrement on each successful union: the component count is then available in O(1) at any moment.

• Always compare roots, never immediate parents. parent[a] == parent[b] is a wrong-answer bug.

• DSU beats DFS specifically when edges arrive incrementally, because DFS must re-traverse after every insertion.

• Basic DSU cannot split sets or answer directed reachability. Offline deletion-only histories can be reversed from the final graph; general dynamic connectivity needs a different design.

Corrective source notes

• Disjoint Set Union - Algorithms for Competitive Programming — Union by rank/size alone gives logarithmic find; the inverse-Ackermann amortized bound uses it together with compression. Checked 2026-10-07.

These citations support the named claims, not blanket certification of the lesson. Worked proofs are derived in the text; execution scope and finite-test limits are recorded separately.