Redirect Courier Roads to Base
Preview mode. Log in to edit, run, submit, and save progress.
Redirect Courier Roads to Base
A courier network has n depots numbered from 0 to n - 1. There are exactly n - 1 directed roads. If road [u, v] is listed, a courier can currently travel from depot u to depot v along that road. Ignoring direction, the roads connect all depots into one network. The emergency base is depot 0, and after repairs every depot must be able to follow directed roads and eventually reach depot 0. You may reverse the direction of any road. Determine the minimum number of road reversals needed so that every depot can report back to base 0. Input Format: You are given n and an array roads, where roads[i] = [from, to]. Output Format: Return the minimum number of roads that must be reversed.
Examples
n = 6 roads = [[0, 1], [1, 3], [2, 3], [4, 0], [4, 5]]
3
Explanation: Road(s) [0, 1], [4, 5], [1, 3] point away while walking from base 0, so 3 road(s) must be reversed.
Approach hint
Think from the base outward.
Common mistake
Skipping assumptions, edge cases, or trade-offs can make an otherwise good answer feel incomplete.