FunctionRacerProblemsRace

Fewest Hops

EasyGraphsPython, JavaScript, TypeScript, Java, C++

A network has n nodes numbered 0 to n - 1. links is a list of pairs [a, b], each a link that can be crossed in either direction. The same pair may appear more than once.

Return the smallest number of links that must be crossed to go from source to goal. Return 0 when source == goal, and -1 when goal cannot be reached from source.

Example 1

n 5
links [[0,1],[1,2],[2,3],[3,4],[0,4]]
source 0
goal 3
returns 2

Going 0 to 4 to 3 crosses 2 links; going through 1 and 2 would take 3.

Example 2

n 4
links [[0,1],[2,3]]
source 0
goal 3
returns -1

Nodes 0 and 3 are in different parts of the network.

Constraints

Race itor take your time

Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.

More Graphs problems