Algoritmos y Estructuras de Datos (VJ1215)

En este ejercicio nos hemos de olvidar de la solución basada en el grado de entrada de los vértices que ya conocemos (algoritmo de Kahn). Buscamos una solución diferente, que no se base en eso sino en el orden en que suceden las cosas durante la búsqueda en profundidad.

En la ordenación topológica que buscamos, para cualquier vértice v, se tiene que cumplir que v esté delante de todos los vértices que sean alcanzables desde v (si un vértice no es alcanzable desde v y v no es alcanzable desde él, no importa si lo ponemos delante o detrás de v).

Fíjate dónde están situadas, en el bosque de llamadas recursivas de la búsqueda en profundidad, las llamadas que visitan los vértices alcanzables desde v respecto de la llamada que visita v. ¿Qué cumplen esas llamadas que podemos aprovechar para conseguir situar a v delante de esos vértices en el resultado?