Is there an algorithm that tell if there is a vertex with an outdegree $\delta^+ \leq 1$ in a strongly connected directed graph in linear complexity? For a certain strongly connected directed graph, i.e. a directed graph where every pair of vertices is connected by an arc, I am looking for a linear complexity algorithm which, by inputting the $\frac{n(n-1)}{2}$ pairs of vertices ordered by the orientation of their arc, can tell if there is a vertex $v$ such as $\delta^+(v) \leq 1$, where $\delta^+(v)$ denotes for the outdegree of $v$.
Obviously the naive algorithm exists, with a complexity $O(n^2)$, which looks at all pairs of vertices.
In the head, for cases where $n \leq 15$ I can figure it out with less than $5n$ steps, but I can't come up with an efficient linear complexity algorithm.
Examples with $n = 5$ :
no such vertex
There's one (vertex 3)
Is there such an algorithm?
 A: Whether or not an $O(n)$ algorithm exists depends heavily on your computational model. (A single-tape Turing machine, for example, would take $O(n^2)$ time even to crawl to the end of the input to look at the edge between vertices $n-1$ and $n$.) But I can give you an algorithm that inspects fewer than $5n$ of the edges to find such a vertex.

Borrowing some language from tournament brackets, we say that vertices $v$ and $w$ "play" if we look at the edge $vw$, and a vertex $v$ "wins" against another vertex $w$ if the edge between them is oriented $w \to v$. As in a double-elimination tournament, two losses eliminate a vertex.
We begin by the following procedure: have vertices $1$ and $2$ play. Then the winner plays vertex $3$. The winner of that plays vertex $4$, and so on. After $n-1$ games, we end up with $n-1$ losers (which have outdegree $1$ already) and a winner.
We can sort the vertices into two groups as we do the procedure above. First put $1$ in group A and $2$ in group B. After that, whenever two vertices play, one of them already has a group, and we put the other vertex in the other group. The result is that the $n-1$ losers are separated into groups A and B, and no two vertices in the same group have played yet.
Repeat the procedure we did two more times. First, for group A (the first two vertices in the group play, then the winner plays the third vertex, and so on.) Second, for group B. This produces the "top A loser" and the "top B loser". Except for them, every vertex in group A or B has lost two games, so it has outdegree $\ge 2$ and is out of consideration. 
We've played $2n-4$ games so far, and now there are only $3$ vertices remaining that could potentially have outdegree $1$ or less: the winner, the top A loser, and the top B loser. So, have each of them play every other vertex. This takes at most $3n$ more steps; realistically, it takes fewer, because some of those games have already been played. After fewer than $5n$ games total, we've either found a vertex with outdegree $\le 1$, or determined that all vertices have outdegree at least $2$.
