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?