progress

~/problems / Graphs / DFS and connected components

Number of Connected Components in an Undirected Graph

On a phone? Coding is easier on a laptop: email this problem to yourself . Meanwhile: quiz this topic or fight a boss.

medium ~20 min

An undirected graph has nodes 0 .. n-1 and a list of edges, where each edge [a, b] joins a and b. Two nodes are in the same component if you can walk from one to the other along edges.

Write count_components(n, edges) -> int: the number of connected components.

count_components(5, [[0, 1], [1, 2], [3, 4]])   # 2   {0, 1, 2} and {3, 4}
count_components(4, [])                         # 4   every node is alone
count_components(3, [[0, 1], [1, 0], [2, 2]])   # 2   repeated edges and self-loops are allowed

Constraints: 1 <= n <= 200_000, 0 <= len(edges) <= 200_000, 0 <= a, b < n. Edges may repeat, and an edge may join a node to itself.

⭐ Bonus: speed tests with 200,000 nodes (one is a single path, far beyond Python's recursion limit) earn a star in O(n + len(edges)) without deep recursion.

Show hint

Every node you reach from a node you haven't seen yet belongs to one new component.

Topic: DFS and connected components. Iterative DFS / flood fill; count and label components.

Read the visual guide
0:00
Ctrl ' run · Ctrl ↵ submit
esc