Let $G= (V,E)$ be a directed graph with $n$ vertices.
A sink is a vertex $s\in V$ such that for all $ v \in V$, $(v,s) \notin E$. Devise an algorithm that, given the adjacency matrix of $G$, determines whether or not $G$ has a sink in time $O(n)$.
Does this pseudocode code look good?
# Input: An adjacency matrix G # Output: True if G has a sink and False if G does not have a sink. Algorithm DetermineSink(G) i←0 j←0 for 0 to len(G) if G[i,j] = 1 ∧ j ≠ i # if there is an edge emanating from i, it is not a sink. return False if G[j,i] = 0 ∧ j ≠ i # there exists no edge and hence it is not a sink return False return True