Problem 2. (Directing edges) You are given an undirected graph G(V,E). Design an efficient algorithm Directions ( ) that can decide whether it is possible to assign directions to the edges such that there is no directed path of length 2 or higher in the graph. That is, every node has either zero indegree or zero outdegree. Boston University - CS330 2/3 Prof. Dora Erdos The algorithm Directions( ) should take as input the adjacency list of graph G (you may assume it is the hash table implementation). It should either return the correctly directed graph (it can be in the form of the adjacency list of a directed graph) or return "not possible to direct". 1. Look at examples of graphs in Figure 1 and try to assign the directions. (You can draw a few examples yourself too) Based on your observations, formulate for what type of graphs it is possible to assign the directions as desired. Your answer should be in the form "Given the graph G(V,E) we can assign directions to the edges in E if and only if ...". (Your answer should be a clear and concise description of your observation. Probably just one or two sentences. You should NOT hand in the solution for the example graphs.) 2. Find and analyze the algorithm Directions( ). Figure 1: Can these three graphs be made into directed graphs with no directed path of length 2 or above