Graphs

Union-Find

Disjoint sets with path compression to merge groups and query connectivity.

Hard, about 90 minutes to practise.

1Understand

The idea

Keep a parent pointer per element; two elements are in the same group when they lead to the same root. union links one root under the other, and find compresses the path as it goes. With union by size or rank, each operation is nearly O(1), which makes "are these connected yet?" cheap as edges arrive.

Intuition

Keep a parent pointer per element; two elements are in the same group when they lead to the same root. union links one root under the other; find compresses the path as it goes so future finds are flat.

With union by size or rank, each operation is nearly O(1). That makes "are these connected yet?" cheap as edges arrive, offline connectivity, Kruskal, and redundant-edge problems.

Path compression + union by rank is the default implementation interviewers expect.

What you will be able to do

  • Implement find with path compression
  • Use union return value to detect cycles

When to use it

  • Dynamic connectivity as edges arrive
  • Count groups after merges
  • Redundant connection / cycle in undirected graph

2See it

Walkthrough

Union by parent

Elements 0..3, union(0,1), union(2,3), find same set?

1 / 5

0
1
2
3
0123

parent[i]=i. find(x) walks up until parent[x]==x (root).

parent = list(range(n))

Live template

Line 1 active

1parent = list(range(n))
2def find(x):
3 while parent[x] != x:
4 parent[x] = parent[parent[x]]; x = parent[x]
5 return x
6def union(a, b):
7 ra, rb = find(a), find(b)
8 if ra == rb: return False
9 parent[ra] = rb; return True

Complexity: time O(α(n)) per op, space O(n)

Almost O(1) per op (inverse Ackermann). Building a full graph and DFS for each edge is slower to write and often O(V + E) per check. Use union-find when connectivity evolves with a stream of unions.

Read the walkthrough as text

Redundant connection. Edges [[1,2],[1,3],[2,3]] form a tree plus one extra.

  1. Init parent [0,1,2,3].
  2. Union 1-2, then 1-3, components merge.
  3. Edge 2-3: find(2) == find(3) already → this edge is redundant; return it.

In code:

  • def find(x):
  • while parent[x] != x:
  • parent[x] = parent[parent[x]]
  • x = parent[x]
  • return x

3Recognise it

Kinds of problems (8)

Same pattern, different surfaces. Each row is a problem shape you should recognise, not only the first walkthrough example.

  • Count components

    Example. Number of connected components in an undirected graph.

    How. Union edges; components = n, successful unions count (with path compression).

  • Redundant connection

    Example. First edge that creates a cycle.

    How. Union on each edge; first edge whose endpoints already share a root.

  • Accounts merge (union by key)

    Example. Union accounts that share an email.

    How. Map email → id; union ids per account; group by root.

  • Union by rank or size

    Example. Keep trees shallow for near-constant find.

    How. Attach smaller rank under larger; path-compress in find.

  • Grid union-find (islands as they appear)

    Example. Dynamic island count as land cells are added.

    How. Union with 4 neighbours when cell flips to land; adjust count on new vs merged.

  • Is the graph a tree? (one component, no cycle)

    Example. Validate n−1 edges connect all nodes acyclically.

    How. n−1 edges and one component after unions, extra edge or disconnect fails.

  • Process edges in value order

    Example. Kruskal-like processing without explicit MST output.

    How. Sort edges by weight; union when endpoints differ.

  • Separate structures per edge type

    Example. Connectivity with multiple edge colours.

    How. One DSU per type, or tag roots by type when merging is type-specific.

Common mistakes

Failure modes the tutor watches for. Open the Common mistake tab in the walkthrough to watch one fail live.

  • Links nodes, not roots

    Why it happens. parent[a]=b directly links the two indices you saw on the edge.

    How it fails. Chain 0→1→2: union(2,3) sets parent[2]=3 but root of 2 is still 0, components wrong.

    Fix. ra, rb = find(a), find(b); if ra != rb: parent[ra] = rb (or union by rank).

  • No path compression

    Why it happens. Find without compression still walks to root correctly.

    How it fails. Skewed parent chain length n, m finds degrade to O(n·m).

    Fix. Path compression: parent[x] = parent[parent[x]] while walking find.

  • Component count drift

    Why it happens. Decrementing on every union call is easy bookkeeping.

    How it fails. union returns false (already connected) but count-- anyway, reaches negative components.

    Fix. Decrement only when find roots differ and union actually merges.

4Check yourself

Concept check

A short quiz on this lesson before you practise. Optional, and it does not gate coding.

Ready to practise?

Mastery comes from solving. The lesson is optional context.

All lessons