Meeting Village
Medium · graph traversal
A valley has n villages, numbered 0 to n - 1, joined by n - 1 two-way footpaths. Each entry of paths is [a, b]. The footpaths are laid out so that you can walk from any village to any other, and there is exactly one way to do it without walking back over a footpath.
The valley wants to hold a market in one village. Walking from one village to another costs one step per footpath. For a village v, its reach is the largest number of steps from v to any village in the valley.
Return the number of the village with the smallest reach. If several villages share the smallest reach, return the lowest number among them. If there is only one village, return 0.
Examples
Example 1
Input: n = 7, paths = [[0, 1], [1, 2], [2, 3], [3, 4], [1, 5], [3, 6]]
Output: 2
Village 2 is at most 2 steps from every village (for example 2 steps to village 5 and to village 6). Villages 1 and 3 each have a village 3 steps away.
Example 2
Input: n = 4, paths = [[0, 1], [1, 2], [2, 3]]
Output: 1
Villages 1 and 2 both have a reach of 2, and 1 is the lower number.
Constraints
- 1 <= n <= 10^5
- len(paths) == n - 1
- paths[i] = [a, b] with 0 <= a, b < n and a != b
- The footpaths connect all the villages and contain no loops.