Ho bisogno del vostro aiuto visto che non riesco a risolvere il seguente esercizio:
Il testo dice:
Progetta un algoritmo che sia in grado di rimuovere tutti i cicli di un grafo orientato G=(V,E) in tempo O(m+n) ,dove m è il numero di archi ed n è il numero di vertici del grafo. Rimuovere un ciclo significa rimuovere un arco del ciclo . Se ci sono l cicli in G il tuo algoritmo dovrebbe rimuovere solo O(l) archi.
Qualcuno di voi ha qualche idea su come devo procedere???
Vi prego illustratemi i passi per la risoluzione dell'esercizio in modo corretto.ù
Io pensavo ad una visita DFS ma non so come applicarla