hubUnion Find

Union Find: when to spot it, explain it, and practice it

Union find shines when the graph is not traversed once but merged repeatedly. If the problem keeps asking whether two things now belong to the same component, DSU is often the right abstraction.

Pattern coverage

30+

Best first move

Map each item to an index before writing DSU code.

Common failure point

Forgetting path compression and getting near-linear operations.

When this pattern should come to mind

The problem is about connectivity after repeated merge operations.

You need to detect whether adding an edge creates a cycle.

Counting connected components matters more than path details.

Checklist before you code

Map each item to an index before writing DSU code.

Use path compression in find and union by rank or size.

Name clearly what a successful union means for the answer.

Count components carefully if unions can fail.

The solving flow that works well in interviews

Initialize each node as its own parent.

Compress paths during find so future queries stay cheap.

Merge roots instead of raw nodes.

Treat a failed union as information, not as an error.

If needed, derive the answer from unique roots or successful unions.

Common variants

Connectivity check

Check whether two nodes are connected after a series of unions.

Cycle detection

If union fails because roots match, the new edge creates a cycle.

Component counting

Track how many connected components remain after merges.

Template preview

PythonPublic preview

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, a, b):
        pa, pb = self.find(a), self.find(b)
        if pa == pb:
            return False
        if self.rank[pa] < self.rank[pb]:
            pa, pb = pb, pa
        self.parent[pb] = pa
        if self.rank[pa] == self.rank[pb]:
            self.rank[pa] += 1
        return True

Classic problems with useful framing

#200

Number of Islands

Medium

Shows how DSU can replace traversal on grids.

Count the number of islands in a grid.

#684

Redundant Connection

Medium

A clean cycle-detection DSU problem.

Find the edge that creates a cycle in an almost-tree graph.

#721

Accounts Merge

Medium

Great for index mapping and component grouping.

Merge account records that share common emails.

#990

Satisfiability of Equality Equations

Medium

Shows how DSU handles constraints instead of edges alone.

Determine whether equality and inequality equations can all be satisfied.

A more useful problem ladder for practice

This is not a random list. It is ordered to help candidates build recognition first, add key variants next, and then increase pressure with harder cases.

Foundation

#684 Redundant Connection

Medium

Find the edge that creates a cycle in an almost-tree graph.

The first edge whose endpoints already connect is exactly the cycle-forming edge.

Foundation

#721 Accounts Merge

Medium

Merge account records that share common emails.

The challenge is mapping string emails to DSU nodes and then grouping by final root.

Variant depth

#990 Satisfiability of Equality Equations

Medium

Determine whether equality and inequality equations can all be satisfied.

Equalities build components; inequalities validate whether the built components are consistent.

High-frequency mistakes

warning

Forgetting path compression and getting near-linear operations.

warning

Unioning raw nodes instead of their roots.

warning

Not normalizing labels when input items are strings or emails.

warning

Counting components without handling duplicate edges correctly.

Recommended practice path

Start with redundant connection and province counting.

Then solve email/account merging problems.

After that, add equation satisfiability or graph grouping questions.

Finally combine DSU with sorting in MST-style questions.