<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>

class Solution
 {
    public:

    /* Questions to ask -
    * 1) What if there any no buses?
    * 2) What if there are no buses from source?
    * 3) What if there are no buses to target?
    * 4) Does a valid path from source to target always exist?
    * 5) Is time a more important constraint than memory in this context?
    * 6) Can two different buses operate between two bus stops?
    * 7) Can two different buses have the exact same route?
    * 8) Is there any time associated with each bus - like arrival and departure time?
    * 9) Can the same bus visit a bus stop again in te same cycle?
    * 
    */

    int numBusesToDestination_1(vector <vector <int>> &routes, int source, int target)
     {
        if (source == target)
            return 0;
        else if (routes.size() == 0)
            return -1;
        
        int num_buses = routes.size();
        int bus_index;

        int num_bus_stops;

        int bus_stop_index_1;
        int bus_stop_index_2;

        int current_bus_stop;

        int count = 0;

        unordered_map <int, unordered_set <int>> adjacency_list;

        unordered_set <int> visited;
        
        queue <int> bus_stops_to_visit;

        for (bus_index = 0; bus_index < num_buses; ++bus_index)
         {
            num_bus_stops = routes[bus_index].size();

            for (bus_stop_index_1 = 0; bus_stop_index_1 < num_bus_stops; ++bus_stop_index_1)
             {
                for (bus_stop_index_2 = bus_stop_index_1 + 1; bus_stop_index_2 < num_bus_stops; ++bus_stop_index_2)
                 {
                    // if (routes[bus_index][bus_stop_index_1] == routes[bus_index][bus_stop_index_2])
                    //     continue;

                    adjacency_list[routes[bus_index][bus_stop_index_1]].insert(routes[bus_index][bus_stop_index_2]);
                    adjacency_list[routes[bus_index][bus_stop_index_2]].insert(routes[bus_index][bus_stop_index_1]);
                 }
             }
         }

        bus_stops_to_visit.push(source);

        while (!bus_stops_to_visit.empty())
         {
            num_bus_stops = bus_stops_to_visit.size();

            for (bus_stop_index_1 = 0; bus_stop_index_1 < num_bus_stops; ++bus_stop_index_1)
             {
                current_bus_stop = bus_stops_to_visit.front();
                bus_stops_to_visit.pop();

                for (int neighbour_bus_stop : adjacency_list[current_bus_stop])
                 {
                    if (neighbour_bus_stop == target)
                        return count + 1;

                    if (visited.find(neighbour_bus_stop) == visited.end())
                     {
                        bus_stops_to_visit.push(neighbour_bus_stop);
                        visited.insert(neighbour_bus_stop);
                     }
                 }
             }

            ++count;
         }

        return -1;
     }

    int numBusesToDestination_2(vector <vector <int>> &routes, int source, int target)
     {
        if (source == target)
            return 0;
        else if (routes.size() == 0)
            return -1;

        int num_buses = routes.size();
        int bus;

        int num_bus_stops;
        int bus_stop;
        // int neighbour_bus_stop;

        int current_bus_stop;

        int min_num_buses = 1;

        unordered_map <int, unordered_set <int>> adjacency_list;

        unordered_set <int> visited_buses;
        unordered_set <int> visited_bus_stops;

        queue <int> bus_stops_to_visit;

        for (bus = 0; bus < num_buses; ++bus)
         {
            num_bus_stops = routes[bus].size();

            for (bus_stop = 0; bus_stop < num_bus_stops; ++bus_stop)
                adjacency_list[routes[bus][bus_stop]].insert(bus);
         }

        bus_stops_to_visit.push(source);
        visited_bus_stops.insert(source);

        while (!bus_stops_to_visit.empty())
         {
            num_bus_stops = bus_stops_to_visit.size();
            // ++min_num_buses;

            for (bus_stop = 0; bus_stop < num_bus_stops; ++bus_stop)
             {
                current_bus_stop = bus_stops_to_visit.front();
                bus_stops_to_visit.pop();

                for (int bus_from_bus_stop : adjacency_list[current_bus_stop])
                 {
                    if (visited_buses.find(bus_from_bus_stop) != visited_buses.end())
                        continue;

                    for (int neighbour_bus_stop : routes[bus_from_bus_stop])
                     {
                        if (neighbour_bus_stop == target)
                            return min_num_buses;
                        else if (visited_bus_stops.find(neighbour_bus_stop) != visited_bus_stops.end())
                            continue;

                        bus_stops_to_visit.push(neighbour_bus_stop);
                        visited_bus_stops.insert(neighbour_bus_stop);
                     }

                    visited_buses.insert(bus_from_bus_stop);
                 }
             }

            ++min_num_buses;
         }

        return -1;
     }

    int numBusesToDestination_3(vector <vector <int>> &routes, int source, int target)
     {
        if (source == target)
            return 0;

        int num_buses = routes.size();
        int bus;

        int num_bus_stops;
        int bus_stop;

        int current_bus_stop;

        int level_size;
        int level_index;

        int min_num_buses = 1;

        unordered_map <int, unordered_set <int>> adjacency_list;

        queue <int> bus_stops_to_visit;

        unordered_set <int> visited_bus_stops;
        unordered_set <int> visited_buses;

        for (bus = 0; bus < num_buses; ++bus)
         {
            num_bus_stops = routes[bus].size();

            for (bus_stop = 0; bus_stop < num_bus_stops; ++bus_stop)
                adjacency_list[routes[bus][bus_stop]].insert(bus);
         }

        if (adjacency_list[source].empty() || adjacency_list[target].empty())
            return -1;

        bus_stops_to_visit.push(source);
        visited_bus_stops.insert(source);

        while (!bus_stops_to_visit.empty())
         {
            level_size = bus_stops_to_visit.size();

            for (level_index = 0; level_index < level_size; ++level_index)
             {
                current_bus_stop = bus_stops_to_visit.front();
                bus_stops_to_visit.pop();

                for (int connecting_bus : adjacency_list[current_bus_stop])
                 {
                    if (visited_buses.find(connecting_bus) != visited_buses.end())
                        continue;
                    else if (adjacency_list[target].find(connecting_bus) != adjacency_list[target].end())
                        return min_num_buses;

                    // num_bus_stops = routes[connecting_bus].size();

                    // for (bus_stop = 0; bus_stop < num_bus_stops; ++bus_stop)
                    for (int bus_stop : routes[connecting_bus])
                     {
                        if (visited_bus_stops.find(bus_stop) != visited_bus_stops.end())
                            continue;

                        bus_stops_to_visit.push(bus_stop);
                        visited_bus_stops.insert(bus_stop);
                     }
                 }
             }

            ++min_num_buses;
         }

        return -1;
     }

    int numBusesToDestination(vector <vector <int>> &routes, int source, int target)
     {
        return numBusesToDestination_3(routes, source, target);
     }
 };
117463