Оптимальный алгоритм с графом

Question

Задание:

Ввод слов:

Let:

Каждое слово может быть представлено как n-2 слов длиной 3 :

Далее: Пусть, у нас есть график G .

1) Если график G не имеют вершины, например, Wi, так что затем поместите это;

2) Для каждой пары вершин добавьте ориентированное ребро или увеличьте вес существующей вершины на 1;

В первой строке ввода мы берем - количество слов;

Вывод: В первой строке выведите V - количество вершин;

Во второй строке выведите E - количество ребер;

В следующей строке выведите слова, соответствующие концамвершина e1 и вес ориентированного ребра;

В следующей строке то же самое для e2

...

До края с номером E

Пример с входом и выходом:

Я написал решение , но оно не было принято из-за " Ограничение памяти " или " Ограничение времени " ( в зависимости откак я выделил память в матрице смежности ). Интересно о лучшем решении , но больше ничего не приходит в голову.По моему скромному мнению, это неплохое решение)

Итак, давайте рассмотрим решение:

1) Моя матрица смежности и базовые типы:

constexpr short increaseSize = 10;
using IndexType = uint16_t;
using MatrixElementType = uint16_t;
using VertexType = string;

---

class Matrix{
    using Vector = std::vector<MatrixElementType>;
    using Data = std::vector<Vector>;
    Data data{};
public:
    auto& operator() (const IndexType i,const IndexType j){
        return data[i][j];
    }
    auto increaseDimension(){
        auto size = data.size();
        bool newSize = false;
        if(size == data.capacity()) newSize = true;
        for(IndexType i = 0;i<size;++i)
        {
            if(newSize)data[i].reserve(size + increaseSize);
            data[i].push_back(0);
        }
        if(newSize)data.reserve(size + increaseSize);
        data.push_back(Vector(size+1,0));
    }
};

2) Вершины:

class Vertices{
public:
    using DataToIndex = std::unordered_map<VertexType,IndexType>;
private:
    DataToIndex dataToIndex{};
public:

    void add(const VertexType& vertex, const IndexType index){
        dataToIndex[vertex] = index;
    }

    const VertexType& getData(const IndexType index){
        for(const auto& element:dataToIndex)
            if(element.second == index) return element.first;
        return dataToIndex.begin()->first;
    }

    auto operator[](const VertexType& data) {
       struct Proxy{
          const IndexType index;
          bool exists;
          operator bool(){return exists;}
       };
    auto iterator = dataToIndex.find(data);
    return Proxy{iterator->second,iterator != dataToIndex.end()};
}

   auto exists(const VertexType& data){
      if(dataToIndex.find(data) == dataToIndex.end())
        return false;
     else return true;
   }
};

3) И наконец, График

class Graph{
using Index = IndexType;
public:
    static constexpr char wordSize = 3;
private:
    Matrix matrix{};
    Vertices vertices{};
    IndexType amoutOfVertices = 0;
    IndexType amountOfEdges = 0;
public:
    inline void addVertex(const VertexType& str){
        if(vertices.exists(str)) return;
        vertices.add(str,amoutOfVertices);
        matrix.increaseDimension();
        ++amoutOfVertices;
    }
    inline void addEdge(const IndexType i,const IndexType j){
        if(matrix(i,j)== 0 ) ++amountOfEdges;
        ++matrix(i,j);
    }
    inline void addEdge(const VertexType& str1,const VertexType& str2){
        auto first = vertices[str1],
             second = vertices[str2];
        if(first && second)
            addEdge(first.index, second.index);
    }

   inline void out(){
        cout << amoutOfVertices << endl;
        cout << amountOfEdges << endl;
        IndexType i,j;
        MatrixElementType element;
        for(i = 0 ;i < amoutOfVertices;++i)
            for(j = 0;j< amoutOfVertices;++j)
                if((element = matrix(i,j))) {
                    cout << vertices.getData(i) << " ";
                    cout << vertices.getData(j) << " ";
                    cout << element << endl;
                }
      }

};

4) Функция для чтения (немного некрасиво, но экономит память):

void readText(){
    Graph graph;
    IndexType T;
    cin >> T;
    getchar();
    for(IndexType mainIndex = 0;mainIndex< T;++mainIndex){
        wordPreparing(graph);
    }
    graph.out();
}


void wordPreparing(Graph& graph ){
    string previousiWord{},iword{};
    char newChar = ' ';
    for(char i = 0;i< Graph::wordSize;++i){
        iword += getchar();
    }
    graph.addVertex(iword);

    newChar = getchar();
    while(newChar != '\n'){
        previousiWord = iword;
        for(char i = 0;i< Graph::wordSize-1;++i)
            iword[i] = iword[i+1];
        iword[Graph::wordSize - 1] = newChar;
        newChar = getchar();
        graph.addVertex(iword);
        graph.addEdge(previousiWord, iword);
    }
}

И мы получаем это:

или его:

Требуется задача: 6,0 с и 128 МБ.

Даже если есть другое решение, я был бы безмерно благодарен, если бы кто-то прокомментировал мой подход)