CODING CHALLENGE · N°29

Union-Find (Connected Components)

Medium GraphsDisjoint SetData Structures

The data structure behind Kruskal’s MST, network connectivity and image-region labeling: a disjoint-set (union-find) that answers "are these two connected?" in near-constant time. Implement it with union by rank and path compression, then count the connected components. Solve it in Python or TypeScript, with hidden tests.

The problem

You are given n nodes labelled 0…n-1 and a list of undirected edges. Two nodes are in the same component if there is a path of edges between them. Return the number of connected components after applying every edge. Implement it with a disjoint-set (union-find) — do not just BFS the graph.

EXAMPLE 1

Input n = 5, edges = [[0,1],[1,2],[3,4]]

Output 2

{0,1,2} and {3,4}

EXAMPLE 2

Input n = 4, edges = []

Output 4

no edges → every node is its own component

EXAMPLE 3

Input n = 3, edges = [[0,1],[1,2],[0,2]]

Output 1

the extra edge is redundant

CONSTRAINTS

1 ≤ n ≤ 10⁵, 0 ≤ edges.length ≤ 10⁵
Use path compression in find and union by rank/size — together they give near-O(1) amortized (inverse-Ackermann) operations.
A redundant edge (both endpoints already in the same set) must not change the count.

SOLVE IT YOURSELF

Your turn — write it

Edit the stub, hit Run (or ⌘/Ctrl + Enter), and watch the hidden tests. Stuck? the hints are right above and Reveal solution is one click away.

YOUR TASK

Implement count_components(n, edges): build a disjoint-set over n nodes, union the endpoints of every edge, then return how many distinct roots remain. Use path compression + union by rank so it scales.

HINTS — 4 IDEAS

Keep a parent array where each node points at another node in its set; a root points at itself.
find(x) walks parents to the root. Compress the path as you go (point nodes straight at the root or their grandparent) so future finds are fast.
union(a, b) finds both roots; if different, attach the smaller-rank tree under the larger to keep trees shallow.
The answer is the number of nodes that are their own root — equivalently, len({find(i) for i in range(n)}).

CPython · WebAssembly

Approach, complexity & discussion — open after you solve

The approach

Each element points to a parent; the root of a chain identifies its set. find follows parents to the root and, with path compression, repoints nodes directly at the root as it returns. union links the two roots, using union by rank/size to attach the smaller tree under the larger so trees stay shallow. Two elements are connected iff find returns the same root.

Complexity

Near O(1) amortized per operation (inverse-Ackermann α(n)) with path compression and union by rank.

Common mistakes

Skipping path compression or union-by-rank — trees degenerate into O(n) chains.
Union-ing the elements directly instead of their roots.
Comparing parents instead of roots to test connectivity.

Where this shows up

Union-Find powers Kruskal’s minimum spanning tree, dynamic connectivity, cycle detection, and region/segment merging in images. Any “are these two in the same group, and merge groups fast” problem reaches for it.

Finished this one? 0 / 75 Challenges done

Explore the topic

See this alongside everything else on the same subject — handbooks, system designs, challenges and tools, in one place.

Algorithms & DSA