Given a directed conected graph which representation is its adjacency matrix $A$, design an algorithm to detect a sink in $\mathcal{O}(V)$ time, being $V$ the number of vertices.
As definitions can vary, in this context, a sink is defined as a vertex with $0$ exit degree and $V-1$ enter degree.
Obviously, the problem is reduced to find a $j\in\{1,\dots,V\}$ such as $a_{ji}=0$ for all $i$ and $a_{ij}=1$ for all $i\not=j$, thats what I tried. However, this solution is in $\mathcal{O}(V^2)$.
Any idea?