Hola Gabriel,
Primero que nada perdón por la respuesta tardía.
Hay unos cuantos problemas con la resolución, paso a detallarte los que veo.
Primero que nada, es correcto que cuando no existe ningún vértice sin aristas incidentes sabemos que hay un ciclo. Sin embargo, no se cumple el recíproco, es decir, si existe algún vértice sin aristas incidentes entonces no hay ciclo. Puede que exista el ciclo de todas maneras. Entonces la idea es que primero intentes calcular el OT, sacando los vértices que van quedando sin aristas incidentes. Si en algún momento no hay más vértices sin aristas incidentes, entonces todos los que restan tienen al menos una, y ahí hay un algoritmo fácil para encontrar un ciclo, que es el que intentaste hacer, pero yendo por las aristas incidentes no las salientes. Me explico mejor.
En la línea 30 estás obteniendo un nodo adyacente por una arista saliente, el problema de esto es que vos la única certeza que tenés es que cada nodo tiene una arista incidente. Entonces en la línea 30 u puede no estar definido, ya que no sabés si tiene una arista saliente. Te pongo un ejemplo, imaginate un ciclo de 3 nodos y a eso sumale una lista de nodos enlazados con aristas en dirección contraria al ciclo. Todos los nodos de la lista tienen una arista incidente, pero no todos tienen una saliente.
Para arreglar este problema tenés que recorrer el grafo "hacia atrás" por las aristas incidentes, y esto se puede hacer con la estructura con dos listas de adyacencia.
Por otro lado, hay otro problema con la solución, y es que los únicos nodos que sabés que si o si tienen aristas incidentes son los que quedaron en el grafo después de "remover" todos los que no entran en el orden topológico. Entonces además de obtener un nodo cualquiera u, tenés que asegurarte que u sea uno de los que tiene al menos una arista incidente.
Saludos,
Guillermo
Primero que nada perdón por la respuesta tardía.
Hay unos cuantos problemas con la resolución, paso a detallarte los que veo.
Primero que nada, es correcto que cuando no existe ningún vértice sin aristas incidentes sabemos que hay un ciclo. Sin embargo, no se cumple el recíproco, es decir, si existe algún vértice sin aristas incidentes entonces no hay ciclo. Puede que exista el ciclo de todas maneras. Entonces la idea es que primero intentes calcular el OT, sacando los vértices que van quedando sin aristas incidentes. Si en algún momento no hay más vértices sin aristas incidentes, entonces todos los que restan tienen al menos una, y ahí hay un algoritmo fácil para encontrar un ciclo, que es el que intentaste hacer, pero yendo por las aristas incidentes no las salientes. Me explico mejor.
En la línea 30 estás obteniendo un nodo adyacente por una arista saliente, el problema de esto es que vos la única certeza que tenés es que cada nodo tiene una arista incidente. Entonces en la línea 30 u puede no estar definido, ya que no sabés si tiene una arista saliente. Te pongo un ejemplo, imaginate un ciclo de 3 nodos y a eso sumale una lista de nodos enlazados con aristas en dirección contraria al ciclo. Todos los nodos de la lista tienen una arista incidente, pero no todos tienen una saliente.
Para arreglar este problema tenés que recorrer el grafo "hacia atrás" por las aristas incidentes, y esto se puede hacer con la estructura con dos listas de adyacencia.
Por otro lado, hay otro problema con la solución, y es que los únicos nodos que sabés que si o si tienen aristas incidentes son los que quedaron en el grafo después de "remover" todos los que no entran en el orden topológico. Entonces además de obtener un nodo cualquiera u, tenés que asegurarte que u sea uno de los que tiene al menos una arista incidente.
Saludos,
Guillermo