815. Bus Routes - cocoder39/coco39_LC GitHub Wiki

815. Bus Routes

Time complexity:

• suppose A routes, each route has B stops, each stop is shared by C routes (C <= A)
• building stop_to_routes: O(A*B)
• building route_connections: O(A * B * C)
• BFS: A nodes and each node has at most A edges so O(A^2)

class Solution:
    def numBusesToDestination(self, routes: List[List[int]], source: int, target: int) -> int:
        if source == target:
            return 0
        
        stop_to_routes = collections.defaultdict(set)
        routes_len = len(routes)
        for i in range(routes_len):
            for stop in routes[i]:
                stop_to_routes[stop].add(i)
        
        route_connections = collections.defaultdict(set)
        for i in range(routes_len):
            for stop in routes[i]:
                route_connections[i].update(stop_to_routes[stop])
        
        source_routes = stop_to_routes[source]
        target_routes = stop_to_routes[target]
        queue = collections.deque(list(source_routes))
        visited_routes = set()
        count = 1
        
        while queue:
            size = len(queue)
            for i in range(size):
                cur_route = queue.popleft()
                if cur_route in target_routes:
                    return count
                visited_routes.add(cur_route)
                for next_route in route_connections[cur_route]:
                    if next_route not in visited_routes:
                        queue.append(next_route)
            count += 1
        return -1