815. Bus Routes (Hard) - TengnanYao/daily_leetcode GitHub Wiki

class Solution:
    def numBusesToDestination(self, routes: List[List[int]], source: int, target: int) -> int:
        if target == source:
            return 0
        h = defaultdict(set)
        routes = [set(route) for route in routes]
        for i, r1 in enumerate(routes):
            h[i].add(i)
            for j in range(i + 1, len(routes)):
                r2 = routes[j]
                if any(x in r1 for x in r2):
                    h[i].add(j)
                    h[j].add(i)
        sources, targets = set(), set()
        for i, route in enumerate(routes):
            if source in route and target in route:
                return 1
            if source in route:
                sources.add(i)
            if target in route:
                targets.add(i)
        result = 1
        seen = set()
        while sources:
            result += 1
            temp = set()
            for num in sources:
                seen.add(num)
                for x in h[num]:
                    if x in targets:
                        return result
                    if x not in seen:
                        temp.add(x)
            sources = temp
        return -1