Vibe Engines Learn
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
  1. Keep a parent array where each node points at another node in its set; a root points at itself.
  2. 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.
  3. union(a, b) finds both roots; if different, attach the smaller-rank tree under the larger to keep trees shallow.
  4. The answer is the number of nodes that are their own root — equivalently, len({find(i) for i in range(n)}).
CPython · WebAssembly

Explore the topic

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

Algorithms & DSA