When an adjacency-matrix representation is used, most graph algorithms require time (V2), but there are some exceptions.

Question:

When an adjacency-matrix representation is used, most graph algorithms require time Ω (V2), but there are some exceptions. Show that determining whether a directed graph G contains a universal sink-a vertex with in-degree |V| - 1 and out-degree 0-can be determined in time O (V), given an adjacency matrix for G.