[Grafi] Esercizio lontani

[Pablitos23]

Dato un grafo G ed un suo nodo s, descrivere un algoritmo che restituisce il numero di nodi raggiungibili da s che si trovano alla massima distanza da s in O(n+m).

Mia idea.
Potremmo effettuare una BFS con s come nodo sorgente.
Ogni volta che visitiamo i nodi di un livello, incrementiamo un contatore, ma viene riazzerato quando passiamo al prossimo livello. Così facendo al termine della BFS avremo il numero di nodi che stanno alla max distanza da s. Tutto ciò sempre in O(n+m).

Può andare? Avete idee migliori??

[apatriarca]

Direi che è più o meno l'algoritmo che ho in mente.

[Pablitos23]

Vabbene grazie.