<p>You are given an array <code>routes</code> representing bus routes where <code>routes[i]</code> is a bus route that the <code>i<sup>th</sup></code> bus repeats forever.</p>

<ul>
	<li>For example, if <code>routes[0] = [1, 5, 7]</code>, this means that the <code>0<sup>th</sup></code> bus travels in the sequence <code>1 -&gt; 5 -&gt; 7 -&gt; 1 -&gt; 5 -&gt; 7 -&gt; 1 -&gt; ...</code> forever.</li>
</ul>

<p>You will start at the bus stop <code>source</code> (You are not on any bus initially), and you want to go to the bus stop <code>target</code>. You can travel between bus stops by buses only.</p>

<p>Return <em>the least number of buses you must take to travel from </em><code>source</code><em> to </em><code>target</code>. Return <code>-1</code> if it is not possible.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> routes = [[1,2,7],[3,6,7]], source = 1, target = 6
<strong>Output:</strong> 2
<strong>Explanation:</strong> The best strategy is take the first bus to the bus stop 7, then take the second bus to the bus stop 6.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> routes = [[7,12],[4,5,15],[6],[15,19],[9,12,13]], source = 15, target = 12
<strong>Output:</strong> -1
</pre>

<p>&nbsp;</p>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= routes.length &lt;= 500</code>.</li>
	<li><code>1 &lt;= routes[i].length &lt;= 10<sup>5</sup></code></li>
	<li>All the values of <code>routes[i]</code> are <strong>unique</strong>.</li>
	<li><code>sum(routes[i].length) &lt;= 10<sup>5</sup></code></li>
	<li><code>0 &lt;= routes[i][j] &lt; 10<sup>6</sup></code></li>
	<li><code>0 &lt;= source, target &lt; 10<sup>6</sup></code></li>
</ul>

from collections import deque
class Solution:
    def numBusesToDestination(self, routes: List[List[int]], source: int, target: int) -> int:
        '''
        minimize number of buses

        buses are connected through stops

        perhaps
        we can tie stops to all of the components/routes they're attached to

        route0: 0 1 2 3
        route1: 0 1 2 5

        0 --> r0, r1
        1 --> r0, r1
        2 --> r0, r1
        3 --> r0, r1

        n = len(routes)
        m = len(route)

        n * m to tie routes to components

        now for adjList
        this is undirected adjList

        we can attach for each component, for each stop, if it's connected to other components create our component adjList


        we have cycles, so directed cyclic graph
        we can consider each route/bus to be it's own component
            all other buses its connected to through stops are really connected to this component

            and we can do bfs on our components
        we don;t care about the number of stops, just the number of buses
        '''
        if source == target:
            return 0
        stopMap = {}
        routesMap = {}
        for idx, route in enumerate(routes):
            routesMap[idx] = set()
            for stop in route:
                routesMap[idx].add(stop)
                if stop not in stopMap:
                    stopMap[stop] = set()
                stopMap[stop].add(idx)
        if source not in stopMap or target not in stopMap:
            return -1
        visitedRoutes = set()
        visitedStops = set()
        queue = deque()
        queue.append((source, 0))
        visitedStops.add(source)
        while len(queue) != 0:
            curr, length = queue.popleft()
            print(curr, length)
            possRoutes = stopMap.get(curr)
            for route in possRoutes:
                if target in routesMap[route]:
                    return length + 1
                else:
                    if route not in visitedRoutes:
                        visitedRoutes.add(route)
                        for stop in routesMap[route]:
                            if stop not in visitedStops:
                                visitedStops.add(stop)
                                queue.append((stop, length + 1))
        return -1
        
        
55026