Ciclo in un grafo

[giuliomontenero]

Ciao a tutti , qualcuno saprebbe dirmi come si fa a trovare un ciclo o più in un grafo?
Io pensavo ad una visita DFS ma non riesco a gestirla per bene in quanto così rischio di eliminare anche archi che non fanno parte del ciclo.

[apatriarca]

Immagino che tu stia sempre cercando di risolvere il problema che hai già postato precedentemente. La visita DFS era la prima cosa ad essermi venuta in mente, ma non avevo visto che parlavi di grafo orientato e quindi non ti avevo risposto ripromettendomi di ripensarci con più attenzione. Immagino che l'idea sia quella di eliminare tutti gli archi che portano da un nodo ad una certa profondità dell'albero DFS ad uno di profondità inferiore. Ovviamente dovrai poi ripetere il procedimento più volte per ogni componente connessa.

[giuliomontenero]

si era questo il problema
problema-algoritmi-su-grafi-t100049.html
ma non capisco bene come faccio ad ottenere tempo O(m+n)