1722. The Most Depots One Run Can Touch

n depots are joined by m one-way routes. A RUN starts at any depot and follows routes forwards for as long as it likes, and it may pass through the same depot more than once. Print the largest number of DISTINCT depots one run can touch.

1->2, 2->3, 3->1, 3->4, 4->5 -> 5 1->2, 2->1, 3->4, 4->3 -> 2 1->2, 2->3, 3->4 -> 4 1->2, 3->2 -> 2

In the first example a run starting at depot 1 goes 1, 2, 3, 4, 5 and touches all five. In the fourth, depots 1 and 3 both feed depot 2 and neither can be reached from the other, so no run touches more than two.

## The three things that have to be said

directed? yes, and reversing one route changes the answer. self-loops? allowed, and a self-loop touches nothing new. parallel routes? allowed, and a second copy adds nothing. disconnected? allowed. The best run lives inside one piece, so the second example answers 2 and not 4.

## What most people try first

A longest path, which is what problem 399 counts on a graph that has no cycles. Here cycles are allowed, and on a graph with a cycle the longest WALK is infinite while the number of distinct depots is finite, so the usual longest-path dynamic program loops forever or returns nonsense. Running it anyway on 1->2, 2->3, 3->1 recurses between the three depots without terminating.

The repair that does not work is marking depots visited during the search and taking the best. That is the longest simple path, which is a different and much harder question, and it also gives the wrong answer here: a run may revisit a depot, and the first example needs the run to pass through depot 3 once but a run on a bigger graph may need to re-cross a cycle to get where it is going.

## Squeeze first, then it is a longest path again

Inside one group of mutually reachable depots, a run can touch EVERY member and finish wherever it likes, because any member reaches any other. And once a run leaves a group it can never come back, because a return route would merge the two groups. So:

touched depots = the group sizes added up along a single path of the SQUEEZED graph, which problem 1720 shows is acyclic

Both directions hold. Any run's distinct depots, collected by group, form a chain of groups in the squeezed graph, and whole groups are at least as good as partial ones. Conversely any chain of groups can be realised by a run that tours each group completely and then steps to the next.

So the answer is the heaviest path of an acyclic graph with group SIZES as weights:

best[c] = size[c] + max(best[d] over squeezed arrows c -> d, or 0 if none) answer = max over c of best[c]

## Why no sort is needed

Kosaraju's pass two hands out group numbers in a topological order of the squeezed graph, so every surviving arrow runs from a smaller group number to a larger one. Filling best from group k down to group 1 therefore always has the values it needs already. Tarjan's numbering is the reverse of one, so with Tarjan the loop runs the other way. Either way the topological sort that problems 380 and 1703 compute separately comes free with the components.

## Related

Problem 399 counts edges on the longest chain of arrows in a graph with no cycles. Problem 1706 maximises a VERTEX WEIGHT along such a chain, where negative weights make a single vertex sometimes best. This problem is the version where cycles are allowed, which is what forces the squeeze; the weights here are group sizes and so are always positive, which is why the answer is never 0 for n at least 1.

## Cost

Time O(n + m): the components, one pass to build the squeezed arrows, one pass for the dynamic program. Space O(n + m). Every search is iterative, since a path of 200000 depots is permitted and recursion on it overflows Python's recursion limit and the default stack in C, C++ and Java. The answer is at most n = 200000, so a 32-bit integer is ample.

Constraints - `1 ≤ n ≤ 200000` - `0 ≤ m ≤ 200000` - `1 ≤ u, v ≤ n` - `u` may equal `v`, so self-loops can occur - the same route may be listed more than once - the map may be disconnected