Introduzione

Bentornato alla serie degli algoritmi sui grafi! Questa volta lavoriamo con un grafo diretto, in cui ogni arco ha una direzione: un arco u -> v significa che u deve venire prima di v.

L'ordinamento topologico dispone i vertici di un grafo diretto aciclico (DAG) in una sequenza tale che ogni arco punti in avanti. Risponde a domande come «in quale ordine posso seguire i corsi, date le relative propedeuticità?»

Il grafo è rappresentato da n (vertici da 0 a n - 1) e edges, un array piatto di coppie dirette [u0, v0, u1, v1, ...], in cui ogni coppia indica u -> v.

Cominciamo!