Strongly Connected Components
Strongly connected components: We now consider a classic application of depthfirst search: decomposing a directed graph into its strongly connected components. This section shows how to do this decomposition using two depthfirst searches. Many algorithms that work with directed graphs begin with such a decomposition. After decomposition, the algorithm is run separately on each strongly connected component. The solutions are then combined according to the structure of connections between components.
A strongly connected component of a directed graph G = (V, E) is a maximal set of vertices C ⊆ V such that for every pair of vertices u and v in C, we have both and ; that is, vertices u and v are reachable from each other. Figure 22.9 shows an example.
Our algorithm for finding strongly connected components of a graph G = (V, E) uses the transpose of G. Given an adjacencylist representation of G, the time to create G^{T} is O(V E). It is interesting to observe that G and G^{T} have exactly the same strongly connected components: u and v are reachable from each other in G if and only if they are reachable from each other in G^{T}. Figure 22.9(b) shows the transpose of the graph in Figure 22.9(a), with the strongly connected components shaded.
The following lineartime (i.e., Θ(V E)time) algorithm computes the strongly connected components of a directed graph G = (V, E) using two depthfirst searches, one on G and one on G^{T}.
STRONGLYCONNECTEDCOMPONENTS (G) 1 call DFS (G) to compute finishing times f[u] for each vertex u 2 compute GT 3 call DFS (GT), but in the main loop of DFS, consider the vertices in order of decreasing f[u] (as computed in line 1) 4 output the vertices of each tree in the depthfirst forest formed in line 3 as a separate strongly connected component
The idea behind this algorithm comes from a key property of the component graph G^{SCC} = (V^{SCC}, E^{SCC}), which we define as follows. Suppose that G has strongly connected components C_{1}, C_{2},..., C_{k}. The vertex set V^{SCC} is {v_{1}, v_{2},..., v_{k}}, and it contains a vertex v_{i} for each strongly connected component C_{i} of G. There is an edge (v_{i}, v_{j}) ∈ E^{SCC} if G contains a directed edge (x, y) for some x ∈ C_{i} and some y ∈ C_{j}. Looked at another way, by contracting all edges whose incident vertices are within the same strongly connected component of G, the resulting graph is G^{SCC}. Figure 22.9(c) shows the component graph of the graph in Figure 22.9(a).
The key property is that the component graph is a dag, which the following lemma implies. 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 these definitions. We can determine articulation points, bridges, and biconnected components using depthfirst search. Let G_{π} = (V, E_{π}) be a depthfirst tree of G.

Prove that the root of G_{π} is an articulation point of G if and only if it has at least two children in G_{π}.

Let v be a nonroot vertex of G_{π}. Prove that v is an articulation point of G if and only if v has a child s such that there is no back edge from s or any descendant of s to a proper ancestor of v.

Let

Show how to compute low[v] for all vertices v ∈ V in O(E) time.

Show how to compute all articulation points in O(E) time.

Prove that an edge of G is a bridge if and only if it does not lie on any simple cycle of G.

Show how to compute all the bridges of G in O(E) time.

Prove that the biconnected components of G partition the nonbridge edges of G.

Give an O(E)time algorithm to label each edge e of G with a positive integer bcc[e] such that bcc[e] = bcc[e′] if and only if e and e′ are in the same biconnected component.