Самая быстрая структура данных для остаточных графов

Я пытаюсь реализовать алгоритм потока с тысячами узлов и ребер, поэтому мне нужны эффективные структуры данных. В настоящее время я делаю следующее:

Structure Node:

Double Linked Array (Parents) //Edges that enter the node (basicaly a tuple that contains a pointer to the parent node and the weight, current flow of the edge
Double Linked Array (Sons) //Edges that leave the node

Проблема в том, что когда я выполняю BFS, задавая узел v, мне нужно посмотреть на ребра в остаточном графе (в основном обратные ребра для ребер, по которым вы посылаете поток), которые выходят из v. Поскольку у меня могут быть параллельные ребра, мне нужно всегда знать, какое обратное ребро исходит из какого прямого ребра.

В настоящее время я решаю эту проблему, сначала обрабатывая все ребра в Sons(v), а затем я определил карту, которая дает мне индекс Parents(w) в узле назначения w всех этих ребер. Таким образом, я получаю обратный край, который я хранил, и могу выполнить свой алгоритм. Однако эти карты имеют время доступа log(E), что сильно замедляет работу моего алгоритма. Как я могу решить эту проблему (двойные связанные списки реализованы как std::vector)?