Find vertices that are in all cycles

A strong student told me about this interesting problem from his programming contest.

There is at least an edge between every pair of distinct vertices of a digraph $G$. Find the cardinality of the set

$$\{v\in V(G):G-v\text{ is acyclic}\}$$ as well as the element of smallest index within it. $G$ could have up to $6000$ vertices.

==================================

Solution:

The student's team uses the result of the previous post. For mine, I notice that every cycle of length at least $4$ contains a shorter cycle. So we can first find a cycle in $O\left(n(G)\right)$ time, then find a cycle $C$ of length at most $3$ in $O\left(\log n(G)\right)$ time. For every candidate vertex in $V(C)$, it is in the final set if and only if $G-v$ is acyclic, which we determine in $O\left(n(G)\right)$ time.