Ciao a tutti,
Questa volta mi sono imbattuto nella risoluzione di vacanze
L’unico approccio che mi e’ venuto in mente e’ quello di listare tutti i cicli di lunghezza 4 (A-B-C-D) del grafo e verificare che non ci sia un arco A-C oppure B-D
Lo implementerei (o meglio, ho provato senza successo ad implementare) con un dfs a partire da ogni nodo, con profondita’ massima di ricorsione a 4, colorando i nodi visitati prima con 1 e poi 2, e facendo backtracking a ogni ciclo valido
Siccome questo mi sembra un problema un po’ troppo complesso per essere il terzo di una territoriale chiedo se ci sono approcci alternativi che mi sono sfuggiti
Grazie in anticipo
Qua puoi trovare la soluzione ufficiale.
Ti lascio come serie di spoiler il mio processo risolutivo per questo problema:
-
Visualizza il grafo coretto
-
Puoi vederlo come un quadrato
-
Un quadrato è composto da lati
-
Presi due lati, gli altri due sono fissati
1 Mi Piace
grazie per gli hint e per la risorsa