Bus Routes

if next_stop == target:

Check if the next stop is the target stop.

Finding the target stop means the shortest path in terms of buses taken has been found, allowing immediate return.

return buses_taken

Return the current bus count as the minimum buses needed.

Returning immediately upon finding the target stop ensures the BFS shortest path property is preserved and the minimal bus count is returned.

stop_to_buses[stop].append(bus)

Append the current bus to the list of buses for this stop.

This line populates the stop-to-bus mapping, enabling quick access to buses from any stop during BFS.

buses_taken += 1

Increment the bus count at the start of each BFS layer.

Each BFS layer corresponds to taking one additional bus, so incrementing here tracks the number of buses taken.

if bus in used_buses:

Skip buses that have already been used.

Avoiding reuse of buses prevents cycles and redundant exploration, ensuring BFS efficiency and correctness.

used_buses.add(bus)

Mark the current bus as used.

Recording the bus as used ensures it won't be considered again in future BFS layers, pruning the search space.

visited_stops.add(next_stop)

Mark the next stop as visited.

Recording visited stops prevents revisiting and infinite loops during BFS traversal.

stop_to_buses = defaultdict(list)

Initialize a dictionary mapping stops to buses that visit them.

This data structure enables O(1) average-time lookup of buses available at any stop, which is critical for efficient BFS traversal.

visited_stops = {source}

Initialize a set to track visited stops.

Tracking visited stops prevents revisiting and infinite loops during BFS.

used_buses = set()

Initialize a set to track buses already taken.

Marking buses as used ensures each bus route is only considered once, avoiding redundant exploration.

stop = queue.popleft()

Dequeue the next stop to process.

FIFO queue ensures BFS explores stops in order of increasing bus transfers.

for bus in stop_to_buses[stop]:

Iterate over all buses that visit the current stop.

Exploring all buses available at the current stop expands the BFS frontier to new stops reachable by taking these buses.

for next_stop in routes[bus]:

Iterate over all stops served by the current bus.

Exploring all stops reachable by the current bus expands the BFS frontier to new stops that can be reached with one more bus transfer.

if next_stop not in visited_stops:

Check if the next stop has not been visited yet.

Only enqueue unvisited stops to prevent cycles and redundant BFS exploration.

queue.append(next_stop)

Enqueue the next stop for BFS exploration.

Adding the stop to the queue schedules it for exploration in the next BFS layers, expanding the search frontier.

if source == target:

Check if source and target stops are the same.

If source equals target, no buses need to be taken, so returning 0 immediately handles this trivial case efficiently.

queue = deque([source])

Initialize BFS queue with the source stop.

Starting BFS from the source models the initial position in the traversal graph.

while queue:

Continue BFS while there are stops to explore.

The loop processes stops layer by layer, corresponding to increasing bus transfers.

for _ in range(len(queue)):

Iterate over all stops at the current BFS level.

Processing all stops at the current bus transfer level ensures BFS explores layer by layer, guaranteeing shortest path in terms of buses taken.

continue

Continue to next bus if current bus is already used.

This control flow prevents processing the same bus multiple times, which could cause infinite loops or redundant work.

return -1

Return -1 if the target stop is unreachable after BFS completes.

If BFS exhausts all reachable stops without finding the target, it proves no route exists, so returning -1 correctly signals impossibility.

for bus, stops in enumerate(routes):

Enumerate each bus route and its stops.

Enumerating routes with indices allows associating stops with their bus IDs, which is necessary for tracking used buses.

for stop in stops:

Iterate through each stop in the current bus route.

Visiting each stop allows building the reverse mapping from stop to buses.

return 0

Return 0 when source equals target.

This early return prevents unnecessary computation when no travel is needed.

buses_taken = 0

Initialize the count of buses taken to zero.

This variable tracks the number of bus transfers made during BFS traversal.