Bus Routes LeetCode solution in Python

1
class Solution:
2
    from collections import defaultdict, deque
3

4
    def numBusesToDestination(
5
        self, routes: List[List[int]], source: int, target: int
6
    ) -> int:
7
        # Base case
8
        if source == target:
9
            return 0
10
        # Creating graph or routes
11
        graph = defaultdict(set)
12

13
        # Since index represents bus_number on a route
14
        # suppose i is bus number and stops are the values present at that index
15
        for bus_number, stops in enumerate(routes):
16
            # for each stop adding buses going to that stop
17
            for stop in stops:
18
                graph[stop].add(bus_number)
19

20
        # Using bfs
21
        bfs = deque([(source, 0)])
22

23
        # visited stops
24
        seen_stops = set()
25
        # visited buses
26
        seen_buses = set()
27

28
        while bfs:
29
            stop, count = bfs.popleft()
30
            # Resulting case
31
            if stop == target:
32
                return count
33

34
            # Since our graph stores all buses going to a stop
35
            # We will iterate for every bus
36
            for bus_number in graph[stop]:
37
                # We dont want to travel in same bus as we might stuck into loop and reach nowhere
38
                if bus_number not in seen_buses:
39
                    seen_buses.add(bus_number)
40

41
                    # Now we are in a bus, so we will travel all the stops that bus goes to but again, we only want to go to stops we haven't visited
42
                    for stop in routes[bus_number]:
43
                        if stop not in seen_stops:
44
                            seen_stops.add(stop)
45
                            bfs.append((stop, count + 1))
46
        return -1