You are given an array routes representing bus routes where routes[i] is a bus route that the ith bus repeats forever.
For example, if routes[0] = [1, 5, 7], this means that the 0th bus travels in the sequence 1 -> 5 -> 7 -> 1 -> 5 -> 7 -> 1 -> ... forever.
You will start at the bus stop source (You are not on any bus initially), and you want to go to the bus stop target. You can travel between bus stops by buses only.
Return the least number of buses you must take to travel from source to target. Return -1 if it is not possible.
Example 1:
Input: routes = [[1,2,7],[3,6,7]], source = 1, target = 6
Output: 2
Explanation: The best strategy is take the first bus to the bus stop 7, then take the second bus to the bus stop 6.
First, we check if $\textit{source}$ and $\textit{target}$ are the same. If they are, we directly return $0$.
Next, we use a hash table $\textit{g}$ to build a mapping from stops to bus routes. For each bus route, we traverse all the stops it passes through and map each stop to that bus route, i.e., $\textit{g}[\textit{stop}]$ represents all bus routes passing through stop $\textit{stop}$.
Then, we check if $\textit{source}$ and $\textit{target}$ are in the stop mapping. If they are not, we return $-1$.
We use a queue $\textit{q}$ to perform a breadth-first search (BFS). Each element in the queue is a tuple $(\textit{stop}, \textit{busCount})$, representing the current stop $\textit{stop}$ and the number of buses taken to reach the current stop $\textit{busCount}$.
We initialize a set $\textit{visBus}$ to record the bus routes that have been visited and a set $\textit{visStop}$ to record the stops that have been visited. Then, we add $\textit{source}$ to $\textit{visStop}$ and $(\textit{source}, 0)$ to the queue $\textit{q}$.
Next, we start the BFS. While the queue $\textit{q}$ is not empty, we take out the first element from the queue, which is the current stop $\textit{stop}$ and the number of buses taken to reach the current stop $\textit{busCount}$.
If the current stop $\textit{stop}$ is the target stop $\textit{target}$, we return the number of buses taken to reach the target stop $\textit{busCount}$.
Otherwise, we traverse all bus routes passing through the current stop. For each bus route, we traverse all stops on that route. If a stop $\textit{nextStop}$ has not been visited, we add it to $\textit{visStop}$ and add $(\textit{nextStop}, \textit{busCount} + 1)$ to the queue $\textit{q}$.
Finally, if we cannot reach the target stop, we return $-1$.
The time complexity is $O(L)$, and the space complexity is $O(L)$, where $L$ is the total number of stops on all bus routes.
publicclassSolution{publicintNumBusesToDestination(int[][]routes,intsource,inttarget){if(source==target){return0;}// Use Dictionary to map stops to bus routesvarg=newDictionary<int,List<int>>();for(inti=0;i<routes.Length;i++){foreach(intstopinroutes[i]){if(!g.ContainsKey(stop)){g[stop]=newList<int>();}g[stop].Add(i);}}// If source or target is not in the mapping, return -1if(!g.ContainsKey(source)||!g.ContainsKey(target)){return-1;}// Initialize queue and visited setsvarq=newQueue<int[]>();varvisBus=newHashSet<int>();varvisStop=newHashSet<int>();q.Enqueue(newint[]{source,0});visStop.Add(source);// Begin BFSwhile(q.Count>0){varcurrent=q.Dequeue();intstop=current[0],busCount=current[1];// If the current stop is the target stop, return the bus countif(stop==target){returnbusCount;}// Traverse all bus routes passing through the current stopforeach(intbusing[stop]){if(visBus.Add(bus)){// Traverse all stops on this bus routeforeach(intnextStopinroutes[bus]){if(visStop.Add(nextStop)){q.Enqueue(newint[]{nextStop,busCount+1});}}}}}return-1;// If unable to reach the target stop, return -1}}