progress

~/problems / Graphs / DFS and connected components

Connect all cities with fewest roads

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

easy ~15 min

Implement build_roads(n, roads) -> list[tuple[int, int]].

Cities 1..n are joined by two-way roads (pairs (a, b); repeats and self-loops may appear). Add as few new roads as possible so every city can reach every other, and return them. Any valid minimum answer is accepted.

build_roads(5, [(1, 2), (3, 4), (4, 1)])
# e.g. [(1, 5)]   cities {1, 2, 3, 4} are already connected, 5 is alone

build_roads(3, [])
# e.g. [(1, 2), (1, 3)]

n and len(roads) go up to 100,000.

⭐ Bonus: a speed test with 100,000 cities earns a star in O(n + len(roads)) without deep recursion (Python's limit is about 1,000 frames).

Show hint

Think about the groups of cities that already reach each other. How few roads join those groups?

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

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