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

enum class State {undiscovered, discovered, visited};

class Solution {
public:
    int numBusesToDestination(vector<vector<int>>& routes, int source, int target) {
        int num_of_routes = routes.size();

		if(source == target) return 0; // no need to take bus if source and target are identical.

		/* unordered_map<stop_ID, unordered_set<bus_route_ID>>,
		unordered_set<bus_route_ID> collects all bus routes that include the given stop (with stop_ID) */
		unordered_map<int, unordered_set<int>> map_of_stop_to_routes;
		for(int route_ID = 0; route_ID < num_of_routes; route_ID++){
			for(int& stop_ID : routes[route_ID]){
				map_of_stop_to_routes[stop_ID].emplace(route_ID);
			}
		}
		/* unordered_map<route_ID, unordered_set<adjacent_route_ID>>
		unordered_set<adjacent_route_ID> collects all routes adjacent to given route_ID.
		If 2 routes are "adjacent", they share at least one stop. In other words, they are interchangeable.
		*/
		unordered_map<int, unordered_set<int>> map_of_route_to_adjacent_routes;
		for(auto& [stop_ID, set_of_route_IDs] : map_of_stop_to_routes){
			for(const int& route_ID :set_of_route_IDs){
				map_of_route_to_adjacent_routes[route_ID].insert(set_of_route_IDs.begin(), set_of_route_IDs.end());
				map_of_route_to_adjacent_routes[route_ID].erase(route_ID); // remove itself from its adjacent routes set
			}
		}

		auto iter_to_src = map_of_stop_to_routes.find(source);
		if(iter_to_src == map_of_stop_to_routes.end()){ // the stop indicated by source is not on any bus route.
			return -1;
		}
		auto iter_to_dest = map_of_stop_to_routes.find(target);
		if(iter_to_dest == map_of_stop_to_routes.end()){ // the stop indicated by target is not on any bus route.
			return -1;
		}

		// multi-source BFS
		vector<State> routes_state (num_of_routes, State::undiscovered);
		queue<int> qq; // qq stores bus route IDs
		unordered_set<int>& set_of_src_routes = iter_to_src->second;
		for(const int& route_ID : set_of_src_routes){
			qq.push(route_ID);
			routes_state[route_ID] = State::discovered;
		} // push all routes having the source as one of its stops into qq

		int num_of_buses_to_take = 0;
		while(!qq.empty()){
			num_of_buses_to_take++;
			int curr_num = qq.size();
			while(curr_num--){
				int route_ID = qq.front();
				qq.pop();
				// route is of type vector, so, have to iterate over it to check if the target stop appears
				for(int& stop_ID : routes[route_ID]){
					if(stop_ID == target){ // target top is indeed on current route
						return num_of_buses_to_take;
					}
				}
				// current route does not contain the target stop
				// get adjacent routes of current route
				unordered_set<int>& set_of_adjacent_routes = map_of_route_to_adjacent_routes[route_ID];
				if(set_of_adjacent_routes.empty()) continue; // no adjacnet routes to current route
				for(const int& adj_route : set_of_adjacent_routes){ // enumerate all adjacent routes 
					if(routes_state[adj_route] != State::undiscovered) continue;
					// push only undiscovered routes into qq
					qq.push(adj_route);
					routes_state[adj_route] = State::discovered;
				}
				routes_state[route_ID] = State::visited;
			}

		}

		// If execution reaches here, it means the target stop cannot be reached
		return -1;
    }
};
149471