Change of routes is what we care about, bus-stops within a route can be abstracted away. We thus have an undirected graph where vertices are route indices and there is an edge 
In this route graph, we want to find the shortest distance between two routes: one containing source and one containing target. So, we use BFS.
If the source is a shared bus-stop, it may belong to multiple routes. So, we start the BFS with a set of source routes. Similarly, if the target is a shared bus-stop, it may belong to multiple routes. So, we terminate once we reach a route that is in the set of target routes.
Building route graph dominates complexity. If there are 
class Solution:
def get_route_graph(self, routes, source, target) -> Tuple[Dict[int, Set[int]], Set[int], Set[int]]:
adj_list = {r: set() for r in range(len(routes))}
source_routes, target_routes = set(), set()
route_buses = []
for i, route in enumerate(routes):
buses = set(route)
for j, r in enumerate(route_buses):
if buses & r:
# route-i shares a bus-stop with route-j
adj_list[j].add(i)
adj_list[i].add(j)
route_buses.append(buses)
if source in buses:
source_routes.add(i)
if target in buses:
target_routes.add(i)
return adj_list, source_routes, target_routes
def numBusesToDestination(self, routes: List[List[int]], source: int, target: int) -> int:
if source == target:
return 0
adj_list, source_routes, target_routes = self.get_route_graph(routes, source, target)
stop_count = 1
q = deque(source_routes)
while q:
level_len = len(q)
for _ in range(level_len):
u = q.popleft()
if u in target_routes:
return stop_count
for v in adj_list[u]:
# source_routes works as visited
if v in source_routes:
continue
source_routes.add(v)
q.append(v)
stop_count += 1
return -1
unreasonably effective 
Leave a comment