5 SiAOD

#include <iostream>
#include <vector>
#include <string>

using namespace std;

class Graph {
private:
    int n; // Кол-во узлов
    int** matrix; // Матрица смежностей
    vector<string> chains; // Вектор простых цепочек графа

public:
    // Создаём объект класса граф
    Graph(int n) {
        this->n = n; // Передаём количесвто узлов

        // Создаём матрицу смежностей
        matrix = new int* [n + 1];
        for (int i = 0; i <= n; i++) {
            matrix[i] = new int[n + 1];
            for (int j = 0; j <= n; j++) {
                matrix[i][j] = 0; // Заполняем матрицу 0
            }
        }
    }

    // Метод добавления не взвешенного ребра
    void addEdge(int first, int second) {
        matrix[first][second] = 1; // Присваиваем новому ребру между узлами first и second в матрице смежности вес равный 1
    }

    // Метод добавления взвешенного ребра
    void addEdgeWithWeight(int first, int second, int weight) {
        matrix[first][second] = weight; // Присваиваем новому ребру между узлами first и second в матрице смежности переданный вес
    }

    // Метод заполнения не взвешенного графа
    void fillGraph() {
        string temp;
    EDGE1:
        cout << "Do you want enter new edge? (y/n) "; // Спрашиваем будет ли пользователь вводить новое ребро
        cin >> temp; // пользователь отвечает на вопрос
        if (temp != "y" && temp != "n") {
            cout << "Try again" << endl;
            goto EDGE1;
        }
        else if (temp == "y") { // если, да
            int first, second;
            cout << "Enter edge:" << endl;
            cout << "first node: ";
            cin >> first; // то вводит первый узел
            cout << "second node: ";
            cin >> second; // вводит второй узел
            addEdge(first, second); // добавляем новое не взвешенное ребро
            goto EDGE1; // повторяем алгоритм
        }
    }

    // Метод заполнения взвешенного графа
    void fillGraphWithWeight() {
        string temp;
    EDGE2:
        cout << "Do you want enter new edge? (y/n) "; // Спрашиваем будет ли пользователь вводить новое ребро
        cin >> temp; // пользователь отвечает на вопрос
        if (temp != "y" && temp != "n") {
            cout << "Try again" << endl;
            goto EDGE2;
        }
        else if (temp == "y") { // если, да
            int first, second, weight;
            cout << "Enter edge:" << endl;
            cout << "first node: ";
            cin >> first; // то вводит первый узел
            cout << "second node: ";
            cin >> second; // вводит второй узел
            cout << "weight: ";
            cin >> weight; // вводит вес
            addEdgeWithWeight(first, second, weight); // добавляем новое взвешенное ребро
            goto EDGE2; // повторяем алгоритм
        }
    }

    // Метод вывода графа как матрицы смежностей
    void printMatrix() {
        if (n > 0) { // Если матрица существует
            cout << "Matrix:" << endl;
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= n; j++) {
                    cout << matrix[i][j] << "\t"; // Выводим вес ребра между узлами i и j
                }
                cout << endl;
            }
        }
    }

    // Метод вывода графа как списка смежностей
    void printList() {
        if (n > 0) { // Если есть хотя бы один узел
            cout << "List:" << endl;
            for (int i = 1; i <= n; i++) { // Перебираем все узлы
                cout << i << ": "; // Выводим номер узла
                for (int j = 1; j <= n; j++) { // Перебираем все узлы
                    if (matrix[i][j] > 0) { // Проверяем на смежность
                        cout << j << " "; // Выводим смежные узлы
                    }
                }
                cout << endl;
            }
        }
    }

    // Метод сохранения и вывода цепочки
    void saveChain(vector<int> chain) {
        string ch = ""; // Создаём строку, в которую занесём цепочку
        for (int node : chain) {
            ch += to_string(node) + "-"; // Записываем цепочку в строку из вектора
        }
        ch.pop_back(); // Убираем лишнее "-" в конце

        string rch = ""; // Создаём строку для перевёрнутой цепочки
        for (int i = 0; i < ch.length(); i++) {
            rch += ch[ch.length() - 1 - i]; // Перевораичваем цепочку и записываем в созданную переменную
        }

        if (find(chains.begin(), chains.end(), rch) == chains.end()) { // Цепочка и перевёрнутая цепочка считаются за одну и ту же цепочку
            chains.push_back(ch); // Если ещё не записывали перевёрнутую, то записываем текущую
            cout << ch << endl; // и выводим её
        }
    }

    // Преобразованный для поиска всех цепочек в графе метод поиска "в глубину" (DFS)
    // Простая цепочка - любой путь, который не включает в себя один и тот же узел дважды
    void dfs(int i, vector<int> chain) {
        chain.push_back(i); // Добавляем узел в цепочку

        for (int j = 1; j <= n; j++) { // Перебираем все узлы
            if (matrix[i][j] > 0) { // Проверяем каждый на смежность с текущим
                if (find(chain.begin(), chain.end(), j) == chain.end()) { // Проверяем, что ещё не проходили, через вершину
                    dfs(j, chain); // Рекурсивно вызываем DFS
                }
            }
        }

        if (chain.size() > 1) { // Если в цепочке больше 1 узла
            saveChain(chain); // Сохраняем её
        }
    }

    // Метод поиска всех цепочек в графе
    void showAllChains() {
        for (int i = 1; i <= n; i++) { // Перебираем все узлы
            vector<int> chain; // Создаём вектор цепочки
            dfs(i, chain); // Начинаем преобразованный поиск "в глубину"
        }
    }

    // Метод нахождения кратчайшего пути методом Флойда
    void minWayByFloyd(int first, int second) {
        int INF = 1000000; // Большое число/бесконечность

        // Создаём матрицу длин кратчайших путей и матрицу детей ("серединных" узлов между искомыми узлами) для прохождения по кратчайшему пути для каждой пары узлов
        int** minWay = new int* [n + 1];
        int** children = new int* [n + 1];
        for (int i = 0; i <= n; i++) {
            minWay[i] = new int[n + 1];
            children[i] = new int[n + 1];
            for (int j = 0; j <= n; j++) {
                if (matrix[i][j] == 0) { // Если нет прямого пути между узлами
                    minWay[i][j] = INF; // то записываем большое число (INF)
                    children[i][j] = 0; // а сюда 0
                    continue;
                }
                minWay[i][j] = matrix[i][j]; // иначе записываем вес
                children[i][j] = j; // и пункт назначения
            }
        }

        // Реализуем метод Флойда
        for (int k = 1; k <= n; k++) {
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= n; j++) {
                    if (i != j && k != i && k != j && minWay[i][k] < INF && minWay[k][j] < INF) {
                        if (minWay[i][j] > minWay[i][k] + minWay[k][j]) { // Если пройти напрямую из i в j "дороже", чем из i в k, а затем из k в j
                            minWay[i][j] = minWay[i][k] + minWay[k][j]; // то записываем в матрицу длин суммму пути из i в k и из k в j
                            children[i][j] = children[i][k]; // а в матрицу детей - узел, в который нужно пойти, чтобы попасть из i в k
                        }
                    }
                }
            }
        }

        /*// Для тестов

        // Вывод матрицы длин кратчайших путей для каждой пары узлов
        cout << "Min Way:" << endl;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                cout << minWay[i][j] << " ";
            }
            cout << endl;
        }
        cout << endl;

        // Вывод матрицы детей
        cout << "Children:" << endl;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                cout << children[i][j] << " ";
            }
            cout << endl;
        }
        cout << endl;
        */

        if (minWay[first][second] != INF) { // Если путь есть
            cout << "Length of the way between " << first << " node and " << second << " node: " << minWay[first][second] << endl; // Вывод длины кратчайшего пути для заданных узлов

            // Вывод кратчайшего пути для заданных узлов
            cout << "Way: ";
            int step = first; // Первый шаг - начальный узел
            cout << step; // Выводим начальный узел
            while (step != second) {
                step = children[step][second]; // Находим следующий шаг по матрице детей
                cout << "->" << step; // Выводим его
            }
            cout << endl;
        }
        else { // Если пути нет
            cout << "No way between " << first << " node and " << second << " node" << endl; // Выводим, что между заданными узлами нет пути
        }
    }
};

int main()
{
    string ans;
    cout << "Hello! Do you want to create graph? (y/n) ";
    cin >> ans;
    if (ans != "y") {
        return 0;
    }
    int nodes;
    cout << "Ok! Enter count of nodes: ";
    cin >> nodes;
    Graph graph(nodes);
TYPE:
    cout << "=================================" << endl;
    cout << "What graph it is?" << endl;
    cout << "1. weighted graph" << endl;
    cout << "2. UNweighted graph" << endl;
    cout << "=================================" << endl;
    cout << "Enter your choice: ";
    int choice1;
    cin >> choice1;
    switch (choice1)
    {
    case 1:
        graph.fillGraphWithWeight();
        break;
    case 2:
        graph.fillGraph();
        break;
    default:
        cout << "Try again" << endl;
        goto TYPE;
    }
MENU:
    cout << "=================================" << endl;
    cout << "What are you want to do?" << endl;
    cout << "1. Enter new edge" << endl;
    cout << "2. Print all simple chains in graph" << endl;
    cout << "3. Find min way between 2 nodes" << endl;
    cout << "4. Print graph as matrix" << endl;
    cout << "5. Print graph as list" << endl;
    cout << "0. Exit" << endl;
    cout << "=================================" << endl;
    cout << "Enter your choice: ";
    int choice2;
    cin >> choice2;
    switch (choice2)
    {
    case 1:
        if (choice1 == 1) {
            graph.fillGraphWithWeight();
        }
        else {
            graph.fillGraph();
        }
        goto MENU;
        break;
    case 2:
        graph.showAllChains();
        goto MENU;
        break;
    case 3:
        int first, second;
        cout << "Enter nodes:" << endl;
        cout << "first: ";
        cin >> first;
        cout << "second: ";
        cin >> second;
        graph.minWayByFloyd(first, second);
        goto MENU;
        break;
    case 4:
        graph.printMatrix();
        goto MENU;
        break;
    case 5:
        graph.printList();
        goto MENU;
        break;
    case 0:
        return 0;
    default:
        cout << "Try again" << endl;
        goto MENU;
    }
}