[Algoritmi] Facile esercizio sui grafi

[Pablitos23]

Dato un grafo trovare in $O(n)$ se il grafo ha il pozzo universale.

Pozzo universale = è un nodo il quale non ha archi uscenti e tutti gli altri nodi hanno un arco verso di lui.

Sto provando a risolverlo in questo modo:

Rappresento il grafo in una matrice di adiacenze aggiungendo due elementi alla fine di ogni nodo che indicano:
- true: se un nodo ha archi uscenti;
- il numero di archi entranti.

Una volta costruita e sistemata in memoria la mia matrice di adiacenza modificata, occuperà $O((n+2)^2)$, ma possiamo trovare il pozzo universale iterando sulla colonna col numero di archi entranti:
se il numero di archi entranti è uguale al numero di nodi-1 e il flag degli archi uscenti è False, allora abbiamo il pozzo universale in $O(n+1)$ nel caso peggiore, ossia $O(n)$.

Può andare??

[BoG3]

Scusa ma se usi una matrice di adiacenza: solo per "popolarla" usi $O(n^2)$. Quindi sei gia' fuori dal tuo $O(n)$.

[vict85]

Non puoi rispondere a una domanda sugli algoritmi costruendo una struttura dati che renda il tuo algoritmo sufficientemente efficiente. Può avere senso farlo quando un'operazione va fatta spesso, ma non puoi farlo a prescindere.
Comunque ho l'impressione che la complessità minima dell'algoritmo richiesto dipenda molto dalla struttura usata.