We can represent World of StarCraft as an undirected graph, with each node corresponding to a planet, and each usable space route corresponding to an edge. Note that only space routes connecting planets under the control of the same race should be considered at all (in other words, space routes ~i~ such that ~R_{A_i} = R_{B_i}~). The ~i~-th friend can then safely complete their objective if and only if node ~Y_i~ is reachable from node ~X_i~.

One possible approach is to consider each friend ~i~ independently, and perform either a BFS (Breadth-First Search) or DFS (Depth-First Search) from node ~X_i~ to check whether ~Y_i~ is reachable. This would require ~\mathcal O(N+M)~ time per friend, resulting in an overall time complexity of ~\mathcal O(K(N+M))~, which is too slow to earn full marks.

To improve on this, we can use the fact that the graph is undirected to observe that, for each connected component in the graph, all nodes in the component are reachable from one another. In other words, friend ~i~ can safely complete their objective if and only if ~X_i~ and ~Y_i~ are part of the same connected component as one another. Therefore, if we can precompute which connected component each node is in, then the friends can be handled in ~\mathcal O(1)~ time each.

Finding all of the graph's connected components may be done in ~\mathcal O(N+M)~ using a process known as floodfill, in which we iterate over all ~N~ nodes in any order, and each time we come across a node whose component has yet to be determined, we perform either a BFS or DFS from it to identify all nodes in its component.