Consultas Teórico/Práctico

Buenas,
Tengo una duda con respecto a la estructura de entrada de los grafos. Particularmente, quería saber si asumimos que tenemos el $G^{rev}$ en $O(1)$  (o si hay alguna forma de ir a los nodos incidentes a otro), o si tenemos que pensar en una representación del grafo que nos permita "revertirlo" en $O(n+m)$.

No sé si se entiende del todo mi pregunta, tipo, quiero saber si asumimos que podemos ir de un nodo $u$ a un nodo $v$ en $O(1)$, o  si tenemos que pensar en una forma de hacerlo en $O(n+m)$ cuando se tiene la relación $(v,u)$ en el grafo. Y así tener el grafo reverso.

Saludos!