Leetcode 833 Solution

class Solution:
    def numBusesToDestination(self, routes: List[List[int]], source: int, target: int) -> int:
        if source == target:
            return 0

        bus_ids = collections.defaultdict(set)
        for i, route in enumerate(routes):
            for stop in route:
                bus_ids[stop].add(i)

        q = collections.deque()
        visited = set()

        for i, route in enumerate(routes):
            if source in route:
                q.append(i)
                visited.add(i)

        step = 0
        while q:
            s = len(q)
            step += 1

            for _ in range(s):
                i = q.popleft()

                if target in routes[i]:
                    return step

                for j in routes[i]:
                    for bus_id in bus_ids[j]:
                        if bus_id in visited:
                            continue

                        q.append(bus_id)
                        visited.add(bus_id)

        return -1