Question

we are given a directed graph, represented as an adjacency list. in which each vertex has at least one incoming edge and one outgoing edge.. we would like to print out for each vertex j the list of vertices pointing into j.... what is the most accurate description of the complexity of computing these quantities in term of n.. the number of vertices and m.. the number of edge...​

Answer 1

Answer:

For the first pass of the initial adjacency list,

we need to create a new adjacency list where each vertex is pointing to another vertex with their adjacent edges, and this operation can be done  in order of time m O(m).

Now  if we create the list by including the disconnected vertices the it may happen that m= 0 and for that the time will be O(m+n)  as O(n) tie is required for creating the list.