We are given a directed graph, which is represented using adjacency list.
For this graph, we are provided with a condition that each vertex has at least 1 incoming edge and 1
outgoing edge.
This means, for any vertex incoming edges can be 1 or greater than 1. But, for every vertex only 1
outgoing edge is allowed.
Lets try to visualize this with the help of some graphs :
Suppose, number of vertices(n) = 3. Then, complete graph for n = 3, will look like this :
If we look at this graph then we will observe that, every vertex have more than 1 outgoing edges. But, it is
mentioned in the question that every vertex have only 1 outgoing edge.
So, this won’t satisfy the given condition. We have to make some adjustments.
All the edges, that are shown in red must be removed. So, after removal of these edges, graph will look
like :
Here, we have 3 vertices and 3 edges, means if we have n vertices then we need n edges to satisfy the
given conditions. Let’s not conclude to this point too early & take another graph with n = 4.
Similary, If we draw complete graph for n = 4. Then it will look like this :
Again, this graph won’t satisfy given conditions. We have to make some adjustments.
All the edges that are shown in red must be removed. After removal, graph will look like this :
Here also, for n=4, we have 4 edges.
From these 2 examples we can conclude that, to satisfy given condition on n vertex directed graph, we
need n edges also.
Now, for each vertex j, we want to print out the list of vertices pointing into j.
For that, let’s try to draw the adjacency list for the above 2 examples with n = 3 & n = 4.
N = 3 N = 4
Here, If we represent a graph with N vertices, then we will have N edges.
So, for every vertex, in order to print out all the nodes that are pointing into j, that will require complete
traversal of adjacency list which will take : O( N + N ) = O(2N) = O(N)
So, doing all this will take O(N).
