Representação ótima de grafos

[Josue Andrade Gomes]

Olá amigos C++ers, puzzle para este domingo:
Seja a seguinte implementação de um grafo.
A lista de vértices como um std::vector e a lista de adjacências como um std::vector de índices do primeiro std::vector.

    std::vector<ValueType> V;
    std::vector<std::vector<size_t>> adj;

Seja esta implementação:

    size_t find_vertex(ValueType const& v) const
    {
        auto it = std::find(V.begin(), V.end(), v);
        if (it != V.end()) {
            std::distance(V.begin(), it);
        }
        return npos;
    }

    size_t add_vertex(ValueType&& v)
    {
        V.emplace_back(v);
        adj.emplace_back(std::vector<size_t>{});
        return V.size() - 1;
    }

    void add_edge(ValueType&& v, ValueType&& w)
    {
        auto iv = find_vertex(v);
        if (iv == npos) {
            iv = add_vertex(std::move(v));
        }
        auto iw = find_vertex(w);
        if (iw == npos) {
            iw = add_vertex(std::move(w));
        }
        adj[iv].push_back(iw);
    }

Código em https://godbolt.org/z/9MYE68fqW

A complexidade de add_edge é O(n) por causa da chamada à std::find em find_vertex. A complexidade de add_vertex é O(1).
No meu caso o número de vértices não é trivial podendo chegar a milhões.
Uma maneira e mitigar isso é mudar a implementação de V para um std::set (ou std::multiset) de uma struct que une o valor e a lista de adjacências:

template<class ValueType>
class Graph {
public:
    struct VertexType {
       ValueType value;
       std::vector<typename std::set<VertexType>::const_iterator> adj;
    };
    std::set<VertexType> V;

    ....
};

As implementações de find_vertex, add_vertex e add_edge seriam todas O(log n).

Quais são as suas opiniões? Sugerem outro caminho?

Abraços,
Josué