[Solved] CSCE-629 Analysis of Algorithms Assignment # 4

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 C₁, C₂, , C_k. The component graph G^c for G is a directed graph of k vertices w₁, w₂, , v_k such that there is an edge from w_i to w_j in G^c if and only if there is an edge from some vertex in C_i to some vertex in C_j. Develop an O(|V |+|E|)-time algorithm that on a given directed graph G = (V,E) produces the component graph G^c for G. Make sure that there is at most one edge between two vertices in the component graph G^c.
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.

1