The reverse of a directed graph G is another directed graph GR with the same vertex set with the property that (u, v) is an edge in G if and only if (v, u) is an edge in GR. Consider the following algorithm that takes the adjacency list A[v1, v2, . . . , vn] of a directed graph G as input and outputs an adjacency list of GR. (An adjacency list A[v1, v2, . . . , vn] is an array indexed by the vertices in the graph. Each entry A[vi ]

contains the list of neighbors of vi .)

procedure reversegraph(A[v1, v2, . . . , vn]) initialize an adjacency list AR[v1, . . . , vn] for each i = 1 . . . n: for each u A[vi ]: add vi to the list AR[u] return AR (a) Briefly justify that if (u, v) is an edge in G, then (v, u) is an edge in G0 . (b) Briefly justify that if (u, v) is not an edge in G, then (v, u) is not an edge in G0 . (c) Analyze the runtime of this algorithm assuming that G has n vertices and m edges.