Bus Routes

routes[i] is the list of stops that bus i drives round, in a loop, for ever. You start at stop source, you want to reach stop target, and you may change buses at any stop two routes share (LeetCode 815).

• Input: routes = [[1,2,7],[3,6,7]], source = 1, target = 6.
• Output: 2 — bus 0 from stop 1 to stop 7, change there, then bus 1 from stop 7 to stop 6.
• Goal: the fewest buses, not the fewest stops. Riding one bus past twenty stops still costs 1.

When no chain of transfers reaches the target, return -1.

Fewest buses is a shortest-path question where every ride costs 1, so it is BFS. The difficulty is choosing what the nodes are.

Why not stop to stop. Joining every pair of stops on a route builds a clique: a route with 10^5 stops would need about 5 × 10^9 edges. The thing to walk is the route, not the pairs.

1. Index the routes: one pass over every stop of every route builds stop → the buses that serve it.
2. Queue stops, count buses: the queue holds stops, and each pass of the outer loop is one more bus taken — so every stop dequeued during that pass costs the same number of rides.
3. Ride each bus once: for the stop at the front of the queue, look at the buses serving it. One already ridden is skipped, because everything it reaches is already known. A new one is marked ridden, and every stop on its route is examined.
4. Stop at the target: the first ride that reaches the target ends the search, and the current count is the answer.
5. Empty queue: no chain of transfers gets there, so return -1.

The two visited sets do different jobs. The bus set is what keeps the work linear — a route is walked at most once in the whole search. The stop set only keeps the queue from holding the same stop twice.

The ring on the left is the stops and the column on the right is the buses, with a line wherever a bus serves a stop — which is exactly the index the code builds in step 1. Riding a bus lights the line into it, then the line out to each stop on its route. The number above a stop is the value of buses when that stop joined the queue, so the moment the target lights up, the answer is already written above it.