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.

Cycle detection in certain digraphs

There is at least an edge between every pair of distinct vertices of a digraph $G$. Then $G$ is acyclic if and only if the indegrees of vertices of $G$ are all distinct.

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

Proof:

$(\Rightarrow)$ Arrange the vertices of $G$ from left to right by topological sort, such that there is not edge from right to left. Hence the $i$-th vertex from the left has indegree $i-1$ for $i\in[n(G)]$.

$(\Leftarrow)$ $G$ has a vertex $v$ of zero indegree, so $G$ cannot have a cycle containing $v$ and $G$ has edges from $v$ to all other vertices. Remove $v$ from $G$ and the remaining graph still has all-distinct indegrees. The statement clearly holds.