Sto tentando di risolvere il problema fuga, ho pensato di risolverlo così:
salvo nel grafo soltanto i collegamenti verdi, eseguo delle DFS segnandomi i collegamenti da cui passo, visitando ogni componente del grafo. Quando trovo un vertice già visitato passando per un collegamento non ancora visitato, interrompo la DFS perché il vertice appartiene ad un ciclo. Rimuovo il collegamento dal grafo e con un altra DFS trovo il percorso che collega i due vertici del collegamento rimosso. A quel punto ho risolto il problema, dato che conosco tutti i nodi di un ciclo.
Sul correttore ottengo 30/100, ho provato ad inventarmi nuovi casi oltre quello di esempio, cercando di creare tutti i casi particolari che mi vengono in mente, ma non riesco a trovare errori.
Ho trascurato qualche particolare e il mio ragionamento non funziona oppure c’è soltanto un’errore nel codice?
Ciao, il restante ti esce Output scorretto o Execution timed out?
Io l’ho appena implementato, ma con un ragionamento diverso e mi esce 70/100. Dopo aver memorizzato nella lista solo i collegamenti verdi, per ogni nodo provo tutti i cammini possibili fino a quando non incontro il nodo da cui siamo partiti e a questo punto interrompo tutti i cicli.
Ottengo risposta errata , per questo ho chiesto qui se il mio ragionamento è giusto
Per il tuo programma, sempre che non l’hai già fatto, potresti migliorarlo per esempio togliendo un nodo già elaborato, perché non farà parte di un ciclo partendo da un altro nodo.
Stai considerando che il grafo in ingresso potrebbe essere non connesso?
Hai verificato che in tutti i casi il tuo programma trovi una soluzione (come garantito dal testo del problema)?
Il mio programma dovrebbe funzionare se il grafo non è connesso.
Ho provato con un assert a vedere se trova sempre una soluzione, e qualcosa stampa sempre.
, per questo ho chiesto qui se il mio ragionamento è giusto