Mean Cat
2 points
Suppose we have a directed graph G = (V,E) with V = {1,2,…,n} and E is presented as an adjacency list. For each vertex u in V, out(u) is a list [v1,v2,…,vk] such that (u,vi) in E for each i in {1,2,…,k.
For each u in V, we wish to compute a corresponding list in(u) = [v1,v2,…,vk'] such that (vi,u) in E for each i in {1,2,…,k'.
Let n be the number of vertices in V and m be the number of edges in E. How long would it take to construct the lists in(u), u in V, from the lists out(u), u in V?