Union-Find (Disjoint Set Union) Explained: Connectivity Made Fast

A wedding with 500 guests. All evening, the same question in different costumes: "is she from the bride's side or the groom's?" And occasionally a discovery — two guests turn out to be cousins — quietly merges two circles into one.

Notice what nobody at the wedding ever needs: the full family tree, the path of relationships between two people. Just two operations, over and over: which group is this person in? and merge these two groups.

Those two operations have their own data structure — union-find (also called DSU, disjoint set union) — and by the end of this lesson it will answer both in practically constant time, using nothing but one humble array.

What would we naturally do?

We know graphs now, so the natural answer: model guests as vertices, "knows" as edges, and answer "same group?" with a traversal — start at one person, explore, see if you reach the other. Correct, and O(V + E) per question.

Where does that hurt? When questions and merges interleave — a stream of "are A and B connected? (now C and D become friends) are E and F connected? ..." — every question re-explores the world from scratch. Friend systems, network connectivity checks, clustering: all this shape.

The wasted work is obvious once named: the groups barely change between questions, yet we recompute them every time. What if we maintained the group membership as merges happen, so each question is a lookup instead of an exploration?

The idea: groups as pointer trees

Here's the design, and it fits in one array. Every element gets a "parent" pointer — parent[x] — and groups are little pointer trees:

• A root points to itself: parent[r] == r. The root is the group's representative — its name tag. (Which member is root is arbitrary; it's a label, not a rank.)
• Same root ⟺ same group. That's the entire semantics.

n = 6
parent = list(range(n))     # [0, 1, 2, 3, 4, 5]
# everyone their own parent: six groups of one, like six strangers

find and union, first draft

find(x) — whose group is x in? Follow parents until someone points to themselves. union(a, b) — merge: find both roots; if they differ, point one root at the other:

def find(x):                 # walk up to the root
    while parent[x] != x:
        x = parent[x]
    return x

def union(a, b):
    ra, rb = find(a), find(b)
    if ra != rb:
        parent[ra] = rb      # one root adopts the other - ONE write!

Look at how little union does: after two finds, merging two groups — of any size — is one pointer write. No copying members, no walking both groups. The tree shape absorbs the merge.

Dry run: watch groups merge

start:        parent = [0, 1, 2, 3, 4, 5]   groups: {0}{1}{2}{3}{4}{5}

union(0, 1):  find(0)=0, find(1)=1 differ -> parent[0]=1
              parent = [1, 1, 2, 3, 4, 5]   groups: {0,1}{2}{3}{4}{5}
union(1, 2):  find(1)=1, find(2)=2 differ -> parent[1]=2
              parent = [1, 2, 2, 3, 4, 5]   groups: {0,1,2}{3}{4}{5}
union(3, 4):  parent = [1, 2, 2, 4, 4, 5]   groups: {0,1,2}{3,4}{5}

find(0): 0 -> 1 -> 2 (root)     find(3): 3 -> 4 (root)
same group? find(0)=2, find(3)=4 -> different -> NO

Follow find(0) with your finger: 0 points to 1, 1 points to 2, 2 points to itself — root found, two hops. It works. But that two-hop walk should make you slightly nervous...

The problem: our trees can become chains

What's the worst thing that can happen to find? Chain unions carelessly — union(0,1), union(1,2), union(2,3)... — and the pointer tree grows into a straight line: 0 → 1 → 2 → 3 → ... find(0) now walks n hops. O(n) per query — we have rebuilt the degenerated BST disaster from lesson 7 in a new costume. Same disease: a tree that forgot to stay bushy.

Two fixes, both two-liners, and each attacks the chain from a different side.

Fix 1 — path compression

Observation: the walk find(0) → 1 → 2 → 3 just LEARNED something expensive — that 0, 1 and 2 all have root 3. Why throw that knowledge away? Re-point everyone on the walked path straight at the root, as you pass:

def find(x):
    while parent[x] != x:
        parent[x] = parent[parent[x]]   # skip a generation (path halving)
        x = parent[x]
    return x

The first find on a long chain pays full price — and flattens the chain for everyone, forever. The next find on any of those nodes: one hop. A data structure that gets faster the more you query it — queries as maintenance.

Fix 2 — union by rank

Compression repairs chains; the second fix stops creating them. When merging two trees, we chose arbitrarily who adopts whom. Think: to keep trees short, should the tall tree hang under the short one, or the short under the tall?

Short under tall — then the combined height stays at the taller tree's height (it grows by 1 only when equals merge). Track an upper bound of each root's height ("rank") and always hang the lower-ranked root below:

class DSU:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n          # height upper bound per root
        self.groups = n              # live group count - free bonus

    def find(self, x):
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]
            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 together (remember this line!)
        if self.rank[ra] < self.rank[rb]:
            ra, rb = rb, ra          # ra = the taller root
        self.parent[rb] = ra         # shorter hangs below taller
        if self.rank[ra] == self.rank[rb]:
            self.rank[ra] += 1       # equals merged: height +1
        self.groups -= 1             # one fewer group in the world
        return True

With both fixes, m operations on n elements cost O(m · α(n)) where α — the inverse Ackermann function — is ≤ 4 for any n that fits in this universe. The honest interview phrase: "effectively constant amortised — formally inverse Ackermann" — precise and humble in seven words. Also notice groups: start at n, minus one per real merge — "how many friend circles?" answered in O(1), for free.

The free bonus: cycle detection

Look again at the line marked "remember this": union returns False when both endpoints already share a root. Translate that into graph language — what does it mean if edge (u, v) arrives and u, v are ALREADY connected?

Some path between them already exists. Adding a direct edge creates a second route — a cycle. So feeding an edge list through DSU detects cycles as a side effect:

def first_cycle_edge(n, edges):
    dsu = DSU(n)
    for u, v in edges:
        if not dsu.union(u, v):      # same root BEFORE merging
            return (u, v)            # this edge closes a loop
    return None

print(first_cycle_edge(5, [(0,1), (1,2), (2,3), (3,0), (3,4)]))

(3, 0)

Verify by eye: 0–1–2–3 already form a path; edge (3, 0) turns the path into a ring. This same check is the beating heart of Kruskal's MST algorithm — sort edges by cost, take each unless DSU says "cycle". Learn DSU once, collect two algorithms.

What if...?

What if I union two elements already in the same group? union returns False and changes nothing — idempotent by design, and that False IS the cycle signal above.

What if I need to UN-merge (delete an edge)? DSU can't, efficiently — merging destroys the information needed to split. If your problem removes connections, DSU alone won't carry it (offline tricks and fancier structures exist, beyond placement scope). Saying this limitation unprompted reads as mastery, not weakness.

What if I need the PATH between two elements? DSU knows membership only — "same circle", never "introduce us". Paths need graph traversal. Structure = contract; this one's contract is two operations.

What if the graph is directed? DSU groups are symmetric — u connected to v means v connected to u — so it detects undirected cycles only. Directed cycle detection needs DFS colouring or Kahn's algorithm (coming in the graphs lessons).

Common mistakes

• Comparing parent[a] == parent[b] instead of find(a) == find(b) — parents aren't roots after a few merges.
• Writing parent[a] = b instead of parent[find(a)] = find(b) — detaches a from its own group instead of merging the groups.
• Skipping both optimisations and claiming O(1) — the naive version degrades to O(n) chains.
• Calling it "exactly O(1)" — it's amortised inverse Ackermann; "practically constant" is the accurate phrase.
• Using DSU for directed-graph cycles.
• Expecting paths out of a membership structure.

How do I recognise union-find problems?

DSU questions arrive dressed as stories. The tell is always the same: groups that merge over time + membership questions.

• "friend circles" / "number of provinces" → count groups (the groups counter).
• "accounts merge" (same email → same person) → union by shared attribute.
• "redundant connection" → first cycle-closing edge (the union-returns-False moment).
• "islands appearing one by one" → dynamic connectivity — DSU's home turf, where traversal would re-explore per query.
• Kruskal's MST → DSU as the cycle-check engine.

Name the structure early — "this is union-find" — and the interview changes tone. Versus traversal: static graph asked once → BFS/DFS is equally good; merges interleaved with queries → DSU.

Quick revision

One thing to remember

Union-find answers exactly two questions — "same group?" and "merge these" — in near-constant time; the moment your problem is groups merging over time, it's DSU.

Practice Zone — PYQs from real selection rounds

Six MCQs, then two applications: counting friend circles, and finding the first cycle-closing edge with a full parent-array trace.

Q1Union-findeasy

Union-find answers which question efficiently?

Asked in

aWhat is the shortest path between two nodes?bAre these two elements in the same group — and can I merge two groups?cWhat is the minimum value in a set?dIs this string a prefix of that one?

Q2Union-findeasy

In the parent-array representation, an element is a ROOT (group representative) when:

Asked in

aparent[x] == x — it is its own parentbparent[x] == 0cIt has the smallest value in its groupdIt was inserted first

Q3Union-findmedium

Path compression speeds up find() by:

Asked in

aSorting the parent arraybRe-pointing every node visited during find directly at the root, flattening the tree for all future queriescCaching the last answerdLimiting groups to 10 members

Q4Union-findmedium

Using union-find to detect a cycle in an UNDIRECTED graph: process each edge (u, v) and declare a cycle when:

Asked in

afind(u) == find(v) BEFORE the union — u and v are already connected, so this edge closes a loopbu equals vcThe union fails with an errordAll edges are processed without incident

Q5Union-findmedium

Union by rank (or size) means:

Asked in

aAlways merging the smaller/shorter tree UNDER the larger one's root, keeping trees shallowbMerging groups in numeric ordercRanking elements by insertion timedRefusing unions that would create a cycle

Q6Union-findhard

Start with 10 separate elements and perform 4 unions, none of them redundant (each merges two DIFFERENT groups). How many groups remain?

Asked in

a4b6 — every effective union reduces the count by exactly onec5dCannot be determined

Hands-on tasks:

FAQ

One array, two operations, near-zero cost. Time to step back and learn the final skill — choosing among everything you now own — Lesson 12: Choosing the Right Data Structure →