He estado estudiando SCC y algoritmos sobre ellos, y he visto que la gente casi siempre menciona que el algoritmo de Kosaraju encuentra el SCC y también los ordena de forma topológica (invertida).

Mi pregunta es: ¿el algoritmo de Tarjan tampoco encuentra un tipo topológico (invertido)? He descubierto que no se menciona (al menos desde donde he leído, excepto wikipedia).

He estado pensando en ello y tengo mucho sentido. Cuando se llama a tarjans_dfs en algún nodo u, todos los SCC a los que se puede acceder desde u se encontrarán antes que el SCC de u. ¿Me equivoco?

Wikipedia dice que en realidad lo encuentra:

"Si bien no hay nada especial sobre el orden de los nodos dentro de cada componente fuertemente conectado, una propiedad útil del algoritmo es que no se identificará ningún componente fuertemente conectado antes que ninguno de sus sucesores. Por lo tanto, el orden en el que los componentes fuertemente conectados están identificado constituye un tipo topológico inverso del DAG formado por los componentes fuertemente conectados ".

¿Es mi idea, o es mucho más conocido que el algoritmo de Kosaraju encuentra el orden topológico que el hecho de que Tarjan también lo hace?