#include <iostream>
#include <string>

using namespace std;

struct Node {
    string mark;
    int* relatedVertex = new int; //0 - отсутствие дуги, любое другое неотрицательное число означает присутствие дуги и её длину
};

class Graph {
public:
    Node* arrayOfNodes;
    int sizeOfGraph = 0;

    void addNode(string mark);
    void addArc(const int& weight, string mark1, string mark2);
    void deleteNode(string mark);
    void deleteArc(string mark1, string mark2);
    void changeMark(string oldMark, string newMark);
    void changeArc(const int& weight, string mark1, string mark2);
};

void Graph::addNode(string mark) {
    short flag = 0;
    for(int i = 0; i < sizeOfGraph; ++i) {
        if(arrayOfNodes[i].mark == mark)
            ++flag;
    }
    if (!flag) {
        Node* arrayOfNodes_temp = new Node[sizeof(Node)]; //Выделяем массив новго размера на 1 узел больше
        arrayOfNodes_temp[sizeOfGraph].mark = mark; //Задаем имя
        arrayOfNodes_temp[sizeOfGraph].relatedVertex[sizeOfGraph] = 0;
        for (int i = 0; i < sizeOfGraph; ++i) {
            arrayOfNodes_temp[sizeOfGraph].relatedVertex[i] = 0; //Oбнуляем массив вершин
            arrayOfNodes_temp[i] = arrayOfNodes[i]; // Копируем в новый массив старые узле
            int* relatedVertex_temp = new int[sizeOfGraph + 1]; //Переделываем массив дуг в каждом узле
            relatedVertex_temp[sizeOfGraph] = 0;
            for (int j = 0; j < sizeOfGraph; ++j) {
                relatedVertex_temp[j] = arrayOfNodes_temp[i].relatedVertex[j];
            }

            delete arrayOfNodes_temp[i].relatedVertex;
            arrayOfNodes_temp[i].relatedVertex = relatedVertex_temp; //Ставим указателя нового массива на место старого
        }

        delete arrayOfNodes;
        arrayOfNodes = arrayOfNodes_temp; //Ставим указателя нового массива на место старого
        ++sizeOfGraph; //Инкрементируем размер графа
    } else {
        cout << "Mark is duplicated!\n";
    }
}

void Graph::addArc(const int& weight, string mark1, string mark2) {
    short flag = 0, index1, index2;
    for(int i = 0; i < sizeOfGraph; ++i) {
        if(arrayOfNodes[i].mark == mark1) {
            flag++;
            index1 = i;
        }
        if(arrayOfNodes[i].mark == mark2) {
            flag++;
            index2 = i;
        }
    }
    if(flag == 2) {
        arrayOfNodes[index1].relatedVertex[index2] = weight;
    } else {
        cout << "Didn't find nodes!\n";
    }
}

int main() {
    Graph graph;
    string newMark = "a", newMark2 = "b", newMark3 = "c" , newMark4 = "d", newMark5 = "e";
    graph.addNode(newMark);
    graph.addNode(newMark2);
    graph.addNode(newMark3);
    graph.addNode(newMark4);
    graph.addNode(newMark5);
    for (int i = 0; i < 10; ++i) {
        newMark2 += i + 81;

        graph.addNode(newMark2);
    }

    graph.addArc(13, "a", "b");
    graph.addArc(7, "a", "d");

    graph.addArc(2, "b", "c");

    graph.addArc(3, "c", "a");
    graph.addArc(3, "c", "e");

    graph.addArc(8, "d", "a");
    graph.addArc(2, "d", "b");
    graph.addArc(5, "d", "c");
    graph.addArc(9, "d", "e");

    graph.addArc(8, "e", "a");

    for(int i = 0; i < graph.sizeOfGraph; ++i) {
        cout << graph.arrayOfNodes[i].mark << endl;
        for(int j = 0; j < graph.sizeOfGraph; ++j) {
            cout << graph.arrayOfNodes[i].relatedVertex[j] << " ";
        }
        cout << endl;
    }
}