Show that given a directed graph already stored in adjacency

Show that, given a directed graph already stored in adjacency matrix form, determining if there is a vertex with in-degree |V|-1 and out-degree 0 can be done in O (|V|) time where |V| is the number of vertices within the graph.

Solution

Here we are looking for a vertex in degree of | V | 1 and out degree of zero. Adjacent matrix where the element of row i represent the edges which are out-going from node i to other nodes and elements in column j represent the edges which are in-coming to node j. Here we need to find vertex k, such that row k has all zero’s and column k has all 1s except for the element in row k (which is a zero).
Now let us start traversing first row and stop at the first 1 that is encountered and in case there is no found then this row is the only possible candidate for a universal sink (because it does not have an edge to any other node, no other node can be a universal sink) and if so then node 1 is a universal sink, otherwise the graph has no universal sink.And our search ends once we find a row of all zero’s thus guaranteeing O(V ) running time. Let us assume during traversing the first row we found the first 1 at column k. Then the values 1 through k 1 in the first row have zeros. This means that no node in 1 through k 1 can be
universal sink because node 1 does not have an edge to any of them. Now moving on from the next remaining nodes we begin examining the next available row j and follow a the steps similar to the first row. if no 1 is encountered, we test the jth column for 1s and terminate asexplained above.
Repeating the above procedure, examining one row at a time from vertices that have not yet been eliminated, we can find whether such vertex can be determined in O(V ) time.