Checking whether a digraph on $n$ vertices contains exactly $10\sqrt{n}$ strongly connected components in NL I am studying now for a test in my complexity course. When I solved previous exams I saw the following question: Prove that the language $L$ of all directed graphs on $n$ vertices that contain exactly $10\sqrt{n}$ strongly connected components is in $NL$. 

We saw in class that checking whether a directed graph contains exactly $C$ strongly connected components is in $NL$ for any fixed $C$, but I thought about this question the whole day and I absolutely have no idea how to do it in $NL$ when then number of SCC required is $10\sqrt{n}$. In the test this question was worth 20 points, so it shouldn't be too hard so I thought that maybe I am missing something important.
Hint: Suppose $C_1,\ldots,C_\ell$ are the connected components and $v_i$ is the minimal vertex in $C_i$. Suppose further that $v_1 &lt; v_2 &lt; \cdots &lt; v_\ell$. Show how to certify the fact that this data is correct in NL by keeping at most two of these indices at a time.

Here are some more details for a slightly simpler problem: verifying whether an undirected graph contains exactly $10\sqrt{n}$ connected components. We keep a counter $k$ of vertices accounted for. Suppose the vertices are numbered $1$ to $n$, and for $t$ going from $1$ to $10\sqrt{n}$, do the following:


Guess a vertex $v_t &gt; v_{t-1}$ (where $v_0 = 0$).
For all $v &lt; v_t$, verify that $v$ is not connected to $v_t$.
For each $v \geq v_t$, guess whether $v$ is connected to $v_t$ or not, and verify the guess; for each vertex connected to $v_t$, increase $k$.


If at the end $k = n$ then all vertices are accounted for, and the graph contains exactly $10\sqrt{n}$ connected components.

I leave the straightforward modification that solves the actual problem to the reader.