For ease of writing, I'm going to say "component" instead of "strongly connected component." This should cause no confusion, since it's the only kind of component we're interested in.
Let $G$ be your directed graph. Let $H$ be the DAG made by contracting every component of $G$ to a single vertex. That is, the vertices of $H$ are the components of $G$ and there's an edge from $x$ to $y$ in $H$ if, and only if, there's an edge in $G$ from the component corresponding to $x$ from the one corresponding to $y$. Write $h(C)$ for the vertex in $H$ that corresponds to the component $C$ in $G$.
Observe that any path in $G$ that visits the maximum possible number of components must correspond to a maximum-length path in $H$, which must run from some source to some sink. So, we need to find the longest paths in $H$. We can't just produce a list of them because there might be exponentially many. So, instead, we assign a label $\ell(x)$ to every $x\in V(H)$ using the following procedure.
- Topologically sort the vertices.
- Set $\ell(x) = 0$ for each sink $x$.
- Working back from the leaves in the topological ordering, set $\ell(x) = 1 + \max\,\{\ell(y_1), \dots, \ell(y_k)\}$ for each vertex $x$ with out-neighbours $y_1, \dots, y_k$.
Note that the topological ordering guarantees that we've already computed $\ell(y_i)$ for each out-neighbour $y_i$. When the labelling is computed, it has the property that, for every vertex $x\in H$, $\ell(x)$ is the length of the longest path from $x$ to a sink in $H$.
Now, produce a graph $H'$ from $H$ as follows.
- Delete every edge $(x,y)$ such that $\ell(x)\neq\ell(y)+1$.
- Let $m = \max\,\{\ell(x)\mid x\text{ is a source in }H\}$ (this is the length of the longest path in $H$).
- Iteratively delete every source $y$ with $\ell(y)<m$.
$H'$ contains exactly the vertices and edges of $H$ that appear in longest paths in $H$ (put another way, $H'$ is the union of all longest paths in $H$). In particular, every path from a source to a sink in $H'$ has length exactly $m$, which is the greatest length of any path in $H$.
Now, produce a graph $G'$ from $G$ as follows.
- Delete from $G$ any component $C$ such that $h(C)\notin H'$.
- Delete from $G$ any edge from component $C_1$ to component $C_2$ if there is no edge $(h(C_1),h(C_2))$ in $H'$.
Finally, let $S\subseteq V(G')$ be the set of all vertices whose components are sources in $H'$ and let $T\subseteq V(G')$ be the vertices in components that are sinks in $H'$. The $S$ $T$ paths in $G'$ are exactly the paths in $G$ that visit the maximum possible number of components. Use your favourite shortest path algorithm to find a shortest one.
Thanks to Bakuriu for suggesting topological sort instead of my ad-hoc algorithm.
