Checking whether a digraph on $n$ vertices contains exactly $10\sqrt{n}$ strongly connected components in NL

Question

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.

Answer 1

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 < v_2 < \cdots < 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:

1. Guess a vertex $v_t > v_{t-1}$ (where $v_0 = 0$).
2. For all $v < v_t$, verify that $v$ is not connected to $v_t$.
3. 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.