Homework 5 1. DFS and strongly connected components (a) What are the minimum and the maximum number of strongly connected components that a directed acyclic graph (DAG) on n nodes can have? Give a tight example matching your bound for each question. (b) Show how the 2-phase DFS-based algorithm for computing strongly connected compo- nents works on the directed graph G shown below; assume vertices are listed in alpha- betical order in each adjacency list, and ties are broken alphabetically. Specifically, show the finishing times after phase 1, and the order in which components are output in phase 2. Draw the component graph of G, and clearly list the components. Homework 5 1. DFS and strongly connected components (a) What are the minimum and the maximum number of strongly connected components that a directed acyclic graph (DAG) on n nodes can have? Give a tight example matching your bound for each question. (b) Show how the 2-phase DFS-based algorithm for computing strongly connected compo- nents works on the directed graph G shown below; assume vertices are listed in alpha- betical order in each adjacency list, and ties are broken alphabetically. Specifically, show the finishing times after phase 1, and the order in which components are output in phase 2. Draw the component graph of G, and clearly list the components