Farthest Village
A valley has n villages numbered 0 to n - 1. roads is a list of pairs [a, b] with a != b; a road can be travelled in both directions, and the same pair may appear more than once. The distance between two villages is the fewest roads on any route between them.
Return the village that is farthest from start among the villages that can be reached from it. If several villages are equally far, return the one with the smallest number. If no other village can be reached from start, return start itself.
Example 1
Village 4 is three roads from 0 (through 1 and 3); every other village is closer.
Example 2
Villages 1, 2 and 3 are all one road away, and 1 has the smallest number.
Constraints
1 <= n <= 500 <= len(roads) <= 1000 <= a, b <= n - 1anda != b0 <= start <= n - 1
Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.
More Graphs problems
- Fewest HopsEasy
- Follow the ArrowsEasy
- Forms a TreeEasy
- Groups After Each MergeEasy
- Largest CrowdEasy
- Loop in the WiringEasy
- Mutual FollowsEasy
- Paint BucketEasy