The algorithm from the lecture:

Noted: we will start at vertex C for DFS.

The test graph in problem 1: start at vertex C.

the biconnected components are:

3. [20 points] There is a very close relationship between biconnected components and articulation points. Namely, the articulation points are exactly the vertices at which two (or more) biconnected components are connected Given this fact, it shouldn't be a big surprise that there is a linear time algorithm that identifies the biconnected components of a graph, and in fact this algorithm is quite similar to the articulation point algorithm Give a modification of the articulation-points algorithm that finds biconnected components in linear time. De- scribe the algorithm (in English; it should only take a few sentences to describe the necessary modifications; 10 points). Simulate it on the example in problem 1, showing enough of a trace of the algorithm's execution to demonstrate that it finds exactly the components you found above (6 points). [Hints: look carefully at the order in which the articulation points algorithm explores edges and discovers articulation points, and relate this to which edges are part of which biconnected components. Among other things, you might want to circle or otherwise mark the biconnected components on the edge list you produced as part of your solution to problem 1 (step (f)). search.] As always, you should discuss both correctness and complexity of your algorithm, but for this problem, only a short paragraph is required for each, not full proofs (~4 points) Initially, focus on the first biconnected component to be completely explored by the depth-first DFS To Find Articulation Points Global initialization: dfscounter-0; v.dfs#--1 for all v. DFS(v): v.dfs# = dfscounter++ // initialization for each edge (v.x) if (x.dfs# -1) /l x is undiscovered DFS(x) v.low min(v.low, x.low) if (x.low >= v.dfs#) print "v is art. pt., separating x" quiv: "if( (v,x) is a back edge)" Why? else if (x is not v's parent) v.low-min(Vlow, x.dfs#) the biconnected component is a maximal biconnected subgraph. John Hopcroft and Robert Tarjan algorithm is used to finding the biconnected components in a graph. in problem 1 following are biconnected components. 1. (IA,BI,(A,F),(B,G),(G,Fl 4.(H,J)