Graphs: Dectect a sink in $\mathcal{O}(V)$

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?

Assumption :There is at most one row which contains all zero's.

You want to find a row of the adjacency matrix $A$ whose all entries are zero's. Simple observation if say the desired row is $k$th than in the $k$th column of adjacency matrix $A$ will contain all ones except the [k,k] index (it is easy to verify ). Let $n$ is the number of rows and columns in the matrix $A$.

Algorithm :

• Start from the top right corner of the matrix $A$.

• If $a_{i,j} = 0$ and $i \neq j$ then it's not your required column, skip this column mean move to $ j-1 $th column (see you have skipped one column in this step, so the number of columns for your search has been reduced).

• if $a_{i,j} = 1$ and $i \neq j$ then it is your required column, but it is not required row (think why ? ) so change the row move to $ i+1 $th keep the column same.

Running time. : In each step you either reducing the number of rows or number of columns, so maximum number of steps is going to be at max $2n$ (number of rows + number of columns ).

StackExchange Computer Science Q#80478, answer score: 2