# strongly connected component

(definition)

**Definition:**
A *strongly connected* *subgraph*, S, of a *directed graph*, D, such that no *vertex* of D can be added to S and it still be strongly connected. Informally, a maximal subgraph in which every vertex is *reachable* from every other vertex.

**Generalization** (I am a kind of ...)

*maximally connected component*, *strongly connected graph*, *connected graph*.

**Aggregate child** (... is a part of or used in me.)

*depth-first search*.

**See also**
*cycle*.

*Note:
If a graph is strongly connected, it has only one strongly connected component. *

*
* The strongly connected components *partition* the vertices in the graph. That is, every vertex is in exactly one strongly connected component.

* After Robert Caswell (caswer01@cs.uwa.edu.au), 3 May 2002.*

Author: PEB

## Implementation

(C++, C, Pascal, Mathematica, and Fortran)
## More information

Transitive closure has a link to **Esko Nuutila** and **Eljas Soisalon-Soininen**, *On finding the strongly connected components in a directed graph* (PostScript®), Information Processing Letters 49 (1993) 9-14. The paper has Tarjan's algorithm, references to other algorithms, and two faster algorithms in Pascal-like pseudo-code.

This has a linear time algorithm for finding strongly connected components:

**Robert E. Tarjan**, *Depth-first search and linear graph algorithms*, SIAM Journal on Computing, 1(2):146-160, 1972.

Go to the
Dictionary of Algorithms and Data
Structures home page.

If you have suggestions, corrections, or comments, please get in touch
with
Paul E. Black.

Entry modified 14 August 2008.

HTML page formatted Tue Dec 6 16:16:33 2011.

Cite this as:

Paul E. Black, "strongly connected component", in
*Dictionary of Algorithms and Data
Structures* [online], Paul E. Black, ed.,
U.S. National Institute of
Standards and Technology. 14 August 2008. (accessed TODAY)
Available from: http://www.nist.gov/dads/HTML/stronglyConnectedCompo.html