a. Write a DFS algorithm to find the bridges and cut vertices of a connected, undirected graph in linear time

d. Show how to compute all articulation points in O.E/ time.

f. Show how to compute all the bridges of G in O.E/ time.

22-2 Articulation points, bridges, and biconnected components Let G (V, E) be a connected, undirected graph. An articulation point of G is a vertex whose removal disconnects G. A bridge of G is an edge whose removal disconnects G. A biconnected component of G is a maximal set of edges such that any two edges in the set lie on a common simple cycle. Figure 22.10 illustrates Chapter 22 Elementary Graph Algorithms Figure 22.10 The articulation points, b and biconnected components of a connected, undi rected graph for use in Problem 22-2. The articulation points are the heavily shaded vertices, the bridges are the heavily shaded edges, and the biconnected components are the edges in the shaded regions, with a bcc numbering shown 22-2 Articulation points, bridges, and biconnected components Let G (V, E) be a connected, undirected graph. An articulation point of G is a vertex whose removal disconnects G. A bridge of G is an edge whose removal disconnects G. A biconnected component of G is a maximal set of edges such that any two edges in the set lie on a common simple cycle. Figure 22.10 illustrates Chapter 22 Elementary Graph Algorithms Figure 22.10 The articulation points, b and biconnected components of a connected, undi rected graph for use in Problem 22-2. The articulation points are the heavily shaded vertices, the bridges are the heavily shaded edges, and the biconnected components are the edges in the shaded regions, with a bcc numbering shown