El primer algoritmo que trabaja en tiempo lineal para resolver este problema fue propuesto por Robert Tarjan en 1970 a base de una búsqueda en profundidad (depth-first search).