815. Bus Routes

link

For all the stop, record which bus will pass by.

Double set for pruning.

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

        M = defaultdict(list)

        for i , ll in enumerate(routes):
            for idx in ll:
                M[idx].append(i)

        visitedStop = set()
        visitedPlace = set()

        dq = deque([source])

        step = 0

        while dq:

            lens = len(dq)

            for _ in range(lens):
                idx = dq.popleft()

                if idx == target:
                    return step

                if idx in visitedPlace:
                    continue

                visitedPlace.add(idx)

                for vv in M[idx]:
                    if vv in visitedStop:
                        continue
                    visitedStop.add(vv)
                    for vvv in routes[vv]:
                        dq.append(vvv)


            step += 1

        return -1