Only need help with b,c,d

6. Gotham City. The mayor of Gotham City has made all the streets of the city one way. We can model the street layout as a directed graph G(V, E), where the vertices V of the graph correspond to street intersections (locations), and the edges E correspond the the roads connecting intersections. So for every pair of distinct vertices u,v V, if there is an edge from u to v, then there is no edge from v to u. Assume a sparse representation for G (a) The mayor claims that one can legally drive from any one location in the city to any other. Show how to verify the mayor's claim using a linear-time algorithm that takes as input the graph G. (b) Suppose the mayor's claim is not necessarily true: that it may not be possible to legally drive from any one location to any other. Let us call a location dominant if you can legally drive from that location to any other location. Said another way, v is dominant if the following property holds: for every location w, one can legally drivie from v to w. Give a linear-time algorithm that outputs all of the dominant locations, given the graph G as input (c) Suppose again that the mayor's claim is not necessarily true Let us call a location v safe if wherever you legally drive starting at v, you can always legally drive back to v. Said another way, v is safe if the following property holds: for every location w, if one can legally drive from v to w, then one can legally drive back from w to v. Give a linear-time algorithm that outputs all of the safe locations, given the graph G as input. (d) Suppose again that the mayor's claim is not necessarily true. Nevertheless, an emergency arises, and you must drive from location s to location t, even though there may not be a legal route from s to t. You want to plan a route that traverses some edges in the graph in the reverse (i.e., illegal) direction. In order to minimize the chance of getting caught by the police, your planned route should minimize the number of illegal edges. The number of legal edges in the route is irrelevant Give a linear-time algorithm that computes a route from s to t that minimizes the number of illegal edges (or reports that no route exists), given the graph G and locations s and t as input Hints: all of the above problems can be very easily solved by using standard algorithms as subroutines; for rt (b), the previous exercise may be useful