Estos subgrafos forman una partición del grafo.Un subgrafo fuertemente conexo es maximal si contiene todos los vértices del grafo o si al agregarle un vértice cualquiera deja de ser fuertemente conexo.El primer algoritmo que trabaja en tiempo lineal para resolver este problema fue propuesto por Robert Tarjan[1] en 1970 a base de una búsqueda en profundidad (depth-first search).Para encontrar los componentes fuertemente conexos se puede utilizar el algoritmo de Kosaraju el cual funciona de la siguiente forma: Seaun grafo dirigido: Las dos búsquedas en profundidad y la construcción del grafo reverso consumen tiempo lineal, de manera que el tiempo total es también lineal.
Un grafo dirigido, y sus componentes fuertemente conexos.
