The cities and flights represent a directed graph with ~N~ nodes, each with ~1~ outgoing edge. For each "component" in the graph (a maximal set of nodes which would be connected to one another if the graph was undirected), the graph structure guarantees that there must be exactly one cycle, with the remaining nodes in the component connecting to that cycle (possible indirectly). An obvious solution would be to start at each node and follow the path until we have reached a node that is already visited, and then stop. Doing so for each node yields an ~\mathcal O(N^2)~ solution which is given 7/23 of the points. To improve on this, we can process one component at a time, finding its cycle and then handling all of its non-cyclic nodes.

We can iterate over the nodes from ~1~ to ~N~. If the answer ~A_i~ for node ~i~ hasn't been computed yet, then we'll process node ~i~'s entire component right away. The first step is to locate any node which is part of the component's cycle. This can be done by repeatedly following edges forward from ~i~, marking nodes as having been visited, until a node ~j~ is reached which has already been visited – this node must be part of the cycle. Next, we need to get the cycle's size ~s~ (the number of nodes which are part of it). We can do this by repeatedly following edges forward from ~j~ until we return ~j~, and counting the number of nodes visited along the way.

Now, for each node ~a~ in the cycle, ~A_a = s~ (if Jaws starts in the cycle, he'll just visit all ~s~ nodes in the cycle). For each non-cyclic node ~b~ which is an additional distance of ~d~ away from any node in the cycle, ~A_b = d+s~ (Jaws will visit ~d~ non-cycle nodes on his way to the cycle, and then visit all ~s~ nodes in the cycle). As such, we can compute the answers for all nodes in the component in linear time using breadth-first search, by pushing all the nodes in the cycle onto a queue, and then expanding outwards from the cycle.

If we're processing node ~x~ and there's an edge from a non-cycle node ~y~ to ~x~, then we can set ~A_y = A_x+1~ and push ~y~ onto the queue. Note that this will require precomputing the list of incoming edges for each node. At the end, we can output the computed values ~A_{1 \dots N}~. The total time complexity of this algorithm is ~\mathcal O(N)~.