La soluzione naive fa 50/100 e non ne parliamo neanche.
Componenti fortemente connesse, fin qui ci sono, ho implementato il kosaraju ed all’inizio pensavo che fosse semplicemente il numero di componenti fortemente connesse, ma era solo una supposizione.
Avevo pensato a vedere quante componenti potessero raggiungere tutte le altre, ma nel caso peggiore (un grafo in cui ogni nodo è una componente) la complessità è uguale (non ho provato comunque).
Qualche hint?
(Dopo aver trovato le componenti fortemente connesse)Prova a pensare come un albero che puoi solo percorrere in discesa. Ogni nodo per essere visitato deve avere un arco che sale. Quindi puoi notare che controllando solo una cosa puoi dire se un DAG rispetta le tue caratteristiche o meno 
.
Io ottengo 100/100 con il kosaraju applicato a una BFS (senza nemmeno sapere che era prima di averlo applicato), in effetti nel caso peggiore la complessità é uguale, migliora nel caso medio e questo sembra bastare
Non so come l’hai risolto tu, però nel mio caso peggiore la complessità dovrebbe essere V+E.