1. Write a program to ?nd the strongly connected components in a digraph.

2. Give an algorithm that ?nds the strongly connected components in only one depth- ?rst search. Use an algorithm similar to the biconnectivity algorithm.

3. The biconnected components of a graph, G, is a partition of the edges into sets such that the graph formed by each set of edges is biconnected. Modify the algorithm in Figure 9.69 to ?nd the biconnected components instead of the articulation points.

4. Suppose we perform a breadth-?rst search of an undirected graph and build a breadth-?rst spanning tree. Show that all edges in the tree are either tree edges or cross edges.

5. Give an algorithm to ?nd in an undirected (connected) graph a path that goes through every edge exactly once in each direction.

6. a. Write a program to ?nd an Euler circuit in a graph if one exists.

b. Write a program to ?nd an Euler tour in a graph if one exists.

7. An Euler circuit in a directed graph is a cycle in which every edge is visited exactly once.

a. Prove that a directed graph has an Euler circuit if and only if it is strongly connected and every vertex has equal indegree and outdegree.

b. Give a linear-time algorithm to ?nd an Euler circuit in a directed graph where one exists.