## Algorithm

Problem Name: 815. Bus Routes

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.
```

Example 2:

```Input: routes = [[7,12],[4,5,15],[6],[15,19],[9,12,13]], source = 15, target = 12
Output: -1
```

Constraints:

• `1 <= routes.length <= 500`.
• `1 <= routes[i].length <= 105`
• All the values of `routes[i]` are unique.
• `sum(routes[i].length) <= 105`
• `0 <= routes[i][j] < 106`
• `0 <= source, target < 106`

## Code Examples

### #1 Code Example with C++ Programming

```Code - C++ Programming```

``````
class Solution {
public:
int numBusesToDestination(vector<vector<int>>& routes, int S, int T) {
if (S == T) {
return 0;
}
unordered_map < int, vector<int>>m(501);  // Stop to Bus
int n = routes.size();
// Build graph Stop-to-Bus
for (int i = 0; i  <  n; ++i) {
for (int j = 0; j  <  routes[i].size(); ++j) {
m[routes[i][j]].push_back(i);
}
}
vector<int>visitedBus(501);
vector<int>visitedStop(1000001);
// BFS
queue < int>cur;
queue<int>next;
for (int& b: m[S]) {
cur.push(b);
}
int count = 1;
while (!cur.empty()) {
int bus = cur.front();
cur.pop();
visitedBus[bus] = 1;
for (int& s: routes[bus]) {
if (s == T) {
return count;
}
if (visitedStop[s]) {
continue;
}
visitedStop[s] = 1;
for (int& b: m[s]) {
if (!visitedBus[b]) {
next.push(b);
}
}
}

if (cur.empty()) {
++count;
swap(cur, next);
}
}
return -1;
}
};
``````
Copy The Code &

Input

cmd
routes = [[1,2,7],[3,6,7]], source = 1, target = 6

Output

cmd
2

### #2 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const numBusesToDestination = function (routes, S, T) {
if (S === T) return 0
const map = {}
const visited = new Array(routes.length).fill(false),
queue = [S]
let rides = 0
for (let i = 0; i  <  routes.length; i++) {
for (const stop of routes[i]) {
if (map[stop] === undefined) {
map[stop] = []
}
map[stop].push(i)
}
}
while (queue.length > 0) {
let size = queue.length
rides += 1
while (size > 0) {
const currStop = queue.shift()
size -= 1
for (const bus of map[currStop]) {
if (visited[bus]) continue
visited[bus] = true
for (const stop of routes[bus]) {
if (stop === T) return rides
queue.push(stop)
}
}
}
}
return -1
}
``````
Copy The Code &

Input

cmd
routes = [[1,2,7],[3,6,7]], source = 1, target = 6

Output

cmd
2

### #3 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def numBusesToDestination(self, routes, starterBus, targetBus):
path, travel, travelTaken, used = collections.defaultdict(set), [starterBus], 0, set()
for i, route in enumerate(routes):
for bus in route:
while travel:
new = []
for bus in travel:
if bus == targetBus:
return travelTaken
for route in path[bus]:
if route not in used:
for nextBus in routes[route]:
if nextBus != bus:
new.append(nextBus)
travelTaken += 1
travel = new
return -1
``````
Copy The Code &

Input

cmd
routes = [[7,12],[4,5,15],[6],[15,19],[9,12,13]], source = 15, target = 12

Output

cmd
-1