Railway Schedule (paths)

Ho provato a risolvere il problema e credo di essere arrivato alla soluzione corretta. La mia implementazione però finisce fuori tempo limite. In poche parole l’algoritmo consiste nel lanciare una dfs per trovare il percorso tra ogni coppia degli M input, “marcarlo” per poter capire se più percorsi si sovrappongono (per poterli contare come un percorso unico nella soluzione). Ho pensato che potesse essere d’aiuto ridurre l’albero prendendo per ogni percorso (inteso come insieme di percorsi che si sovrappongono) un nodo rappresentante collegandogli tutti gli archi in uscita per ridurre il numero di passaggi di ogni dfs. Non sono però sicuro che questa soluzione possa rientrare nel tempo a disposizione. Qualcuno è riuscito a risolverlo in altro modo?
Grazie.

Ciao, ci sono più modi per ridurre la complessità, il più semplice è utilizzare un algoritmo di LCA per “spezzare” i percorsi in due e poi usare UFDS per unire i percorsi che si soprappongono.

1 Mi Piace

Ciao e grazie per la risposta.
La seconda parte (quella dell’UFDS) mi torna ma non mi è chiara la parte dello “spezzare” i percorsi in due. Intendi dire che quello che mi conviene fare è cercare il LCA dei nodi “partenza” e “destinazione” per poter analizzare separatamente il tragitto partenza-LCA e LCA-destinazione per poi unire tutti i nodi (o gruppi di nodi) attraversati dai due percorsi?

I percorsi, come vengono dati in input, sono scomodi da processare, però se li spezziamo nel loro lca abbiamo due percorsi entrambi orientati verso la radice. Quindi dato che tutti i percorsi sono orientati ugualmente possiamo processati tutti insieme anziché eseguire una dfs ogni volta.

1 Mi Piace