# 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, Java, and Mathematica)
## 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 Black.

Entry modified 12 August 2019.

HTML page formatted Mon Aug 12 09:59:40 2019.

Cite this as:

Paul E. Black, "strongly connected component", in
*Dictionary of Algorithms and Data Structures* [online], Paul E. Black, ed. 12 August 2019. (accessed TODAY)
Available from: https://www.nist.gov/dads/HTML/stronglyConnectedCompo.html