Information Processing Letters 74 (2000) 107–114Path-based depth-first search for strong andbiconnected componentsHarold N. Gabow1Department of Computer Science, University of Colorado at Boulder, Boulder, CO 80309, USAReceived 19 October 1999; received in revised form 1 March 2000Communicated by S.E. HambruschKeywords: Graph; Depth-first search; Strongly connected component; Biconnected component; Stack; Algorithms1. IntroductionDepth-first search, as developed by Tarjan and co-authors, is a fundamental technique of efficient al-gorithm design for graphs [23]. This note presentsdepth-first search algorithms for two basic problems,strong and biconnected components. Previous algo-rithms either compute auxiliary quantities based on thedepth-first search tree (e.g., LOWPOINT values)or re-quire two passes. We present one-pass algorithms thatonly maintain a representation of the depth-first searchpath. This gives a simplified view of depth-first searchwithout sacrificing efficiency.In greater detail, most depth-first search algorithms(e.g., [23,10,11]) compute so-called LOWPOINT val-ues that are defined in terms of the depth-first searchtree. Because of the success of this method LOW-POINT values have become almost synonymous withdepth-first search. LOWPOINT values are regarded ascrucial in the strong and biconnected component algo-rithms, e.g., [14, pp. 94, 514]. Tarjan’s LOWPOINTmethod for strong components is presented in texts [1,7,14,16,17,21]. The strong component algorithm ofKosaraju and Sharir [22] is often viewed as conceptu-1Email: [email protected] simpler but it requires two passes over the graph.It is presented in texts [2,4,6,25]. Tarjan’s LOW-POINT biconnectedcomponentalgorithm is presentedin texts [1,2,4,5,7,13,14,16,17,21,25]. A two-pass bi-connected component algorithm of Micali that avoidsLOWPOINT values is sketched in [7, pp. 67–68].This paper presents strong and biconnected compo-nent algorithms that are based on the depth-firstsearchpath. This natural approach appears to have first beenproposed by Purdom [19] and Munro [18] for strongcomponents. It is regarded as requiring an extra datastructure for set merging in order to be asymptoticallyefficient, and hence unlikely to be efficient in prac-tice [23]. We present linear-time implementations ofthis approach for both strong and biconnected compo-nents. Our implementations use only stacks and arraysas data structures. A line-by-line pseudocode compar-ison of our algorithms with the tree-based algorithmsof [23] shows the two approaches are similar in termsof lower level resourceusage; performance differencesare likely to be small or platform-dependent.Our algo-rithmsshow that the simpler path-basedview of depth-first search suffices for these properties.One can design other path-based depth-first searchalgorithms for properties such as ear decomposi-tion [15], st-numbering [7], topological numbering,0020-0190/00/$ – see front matter  2000 Published by Elsevier Science B.V. All rights reserved.PII:S0020-0190(00)00051-X108 H.N. Gabow / Information Processing Letters 74 (2000) 107–114Fig. 1. (a) Digraph G. (b)–(e) Path P (solid edges) in the first several steps of the algorithm. Strong component {3} is output in (d).etc. The complete version of this paper [8] includes analgorithm to find the bridges of an undirected graph,leading to an immediate proof of Robbins’ Theo-rem [20]. It also includes a simple articulation pointsalgorithm, and a previously unpublished strong com-ponent algorithm of Tarjan that can be interpreted aspath-based.Section 2 presents our strong component algorithmand Section 3 presents the biconnected componentalgorithm. Appendix A proves a simple property ofbiconnected components. We conclude this sectionwith some terminology.Singleton sets are usually denoted by omitting setbraces, e.g., for a set S and element x, S − x denotesS −{x}. We assume all input graphs contain n verticesand m edges.We use the following operations to manipulate astack S: PUSH(x, S) adds x to S at the (new) top of S.POP(S) removes the value at the top of the stack andreturns that value. TOP(S) is the index of the value atthe top of the stack. Hence S[TOP(S)] is the value atthe top of the stack.2. Strong componentsConsider a digraph G = (V , E). Two vertices arein the same strong component of G if and only ifthey are mutually reachable, i.e., there is a path fromeach vertex to the other. The strong component graphis formed by contracting the vertices of each strongcomponent. Equivalently the strong component graphis the acyclic digraph, formed by contracting verticesof G, that has as many vertices as possible. In short wesay the strong component graph is the finest acycliccontraction of G.This characterization suggests the following high-level algorithm to find the strong component graph ofG = (V , E). See Fig. 1. The algorithm maintains agraph H that is a contraction of G with some verticesdeleted. It also maintains a path P in H . Initially H isthe given graph G.If H has no vertices stop. Otherwise start a newpath P by choosing a vertex v and setting P = (v).Continue by growing P as follows.To grow the path P = (v1,...,vk) choose an edge(vk,w) directed from the last vertex of P anddothefollowing:• If w/∈ P ,addw to P , making it the new last vertexof P . Continue growing P .• If w ∈ P ,sayw = vi, contract the cycle vi,vi+1,...,vk, both in H and in P . P is now a path in thenew graph H . Continue growing P .• If no edge leaves vk, output vkas a vertex of thestrong component graph. Delete vkfrom both Hand P .IfP is now nonempty continue growing P .Otherwise try to start a new path P .It is easy to see that this algorithm forms the finestacyclic contraction of G. (For instance if no edgeH.N. Gabow / Information Processing Letters 74 (2000) 107–114 109Fig. 2. (a)–(d) show the data structure for Fig. 1(b)–(e), respectively. Stack S is shown. Arrows to the left of S represent stack B. Arrows to theright of S represent the entries of I that are used in contract steps. For example, in (a) the algorithm reads I [2]=2 and then contracts cycle2, 4, 5 to get (b). In (c) I [3] changes from 6 to 7, the latter being the strong component number of vertex 3.leaves vkthen vkis a vertex of the finest acycliccontraction.) Thus the algorithm correctly computesthe strong components.This high-level algorithm was originally proposedby Purdom [19] and Munro [18]. The time for an ef-ficient