1. Another way to perform topological sorting on a directed acyclic graph G = (V,E) is to repeatedly find a vertex of in-degree 0, output it, and remove it and all of its outgoing edges from the graph. Develop an O(|V | + |E|)-time algorithm using this approach. Your algorithm should also be able to tell when the input graph has cycles.
2. Let G be a directed graph with strongly connected components C1, C2, ..., Ck. The component graph Gc for G is a directed graph of k vertices w1, w2, ..., vk such that there is an edge from wi to wj in Gc if and only if there is an edge from some vertex in Ci to some vertex in Cj. Develop an O(|V |+|E|)-time algorithm that on a given directed graph G = (V,E) produces the component graph Gc for G. Make sure that there is at most one edge between two vertices in the component graph Gc.
3. Given a linear-time algorithm that takes as input a directed acyclic graph G and two vertices s and t, and returns the number of simple paths from s to t in G. Your algorithm needs only to count the simple paths, not list them. Note that different paths from s to t may share common vertices.
