Suppose you are given the adjacency matrix representation M of a directed graph G = (V,E). Note that the size of M is Θ(n2). The goal here is to determine if there is a node of G with in-degree n−1 and out-degree 0 (that is, all other nodes point to it and it points to no other node). Give an algorithm to do this which runs in Θ(n) time, not Θ(n).

Answer rating: 100% (QA)

Suppose you have an M matrix which is an approximation matrix of graphs where M i j is 1 if and only ... View the full answer