LC815. Bus Routes

class Solution:
    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:
        """ tc O(stops)     sc O(stops)
        BFS on Bus(route), not on stops
        1. map stops to route
        2. BFS: take a stop and find all connected route, start from source stop, at its route, check unvisited route's each unvisited stops (mark current stop  visited and add cache current stop with additional cost for next level traversal)
        3. do this until find current stop == T; otherwise return -1 
        """
        stop_to_route = defaultdict(set)
        for i,route in enumerate(routes):
            for stop in route:
                stop_to_route[stop].add(i)
        
        q = [[S,0]]
        #q = collections.deque()
        #q.append((S,0))
        seen = set([S])
        #seen_route = set()
        #while q:
         #   stop,cost = q.popleft()
        for stop,cost in q:
            if stop == T:
                return cost 
            for route in stop_to_route[stop]:
                # if route in seen_route: continue 
                for stop in routes[route]:
                    if stop not in seen:
                        q.append((stop,cost+1))
                        seen.add(stop)
                routes[route] = []
                # seen_route.add(route)
        return -1