---

#include <iostream>
#include <conio.h>
#include <chrono>
#include <cmath>
#include <ctime>
#include <vector>
#include <limits>
#include <iomanip>
#include <algorithm>

using namespace std;
using namespace std::chrono;

// ============================================================
// СТРУКТУРЫ И КЛАССЫ (глобальные)
// ============================================================

// Edge structure
struct Edge {
    long long u, v, weight;
    Edge(long long _u, long long _v, long long _w) : u(_u), v(_v), weight(_w) {}
    bool operator<(const Edge& other) const {
        return weight < other.weight;
    }
};

// DSU (Disjoint Set Union)
class DSU {
private:
    vector<long long> parent, rank;
public:
    DSU(long long n) {
        parent.resize(n + 1);
        rank.resize(n + 1, 0);
        for (long long i = 1; i <= n; i++) parent[i] = i;
    }
    long long find(long long x) {
        if (parent[x] != x)
            parent[x] = find(parent[x]);
        return parent[x];
    }
    bool unite(long long x, long long y) {
        long long rx = find(x), ry = find(y);
        if (rx == ry) return false;
        if (rank[rx] < rank[ry]) swap(rx, ry);
        parent[ry] = rx;
        if (rank[rx] == rank[ry]) rank[rx]++;
        return true;
    }
};

// ============================================================
// ПРОТОТИПЫ ФУНКЦИЙ
// ============================================================

// Сортировки
void selectionSort();
void bubbleSort();
void insertionSort();
void binaryInsertionSort();
void mergeSort();
void quickSort();

// Вспомогательные функции для Merge Sort
void mergeOptimized(vector<int>& arr, vector<int>& temp, long long left, long long mid, long long right);
void mergeSortRecursiveOpt(vector<int>& arr, vector<int>& temp, long long left, long long right);

// Вспомогательные функции для Quick Sort
long long partition(vector<int>& arr, long long low, long long high);
void quickSortRecursive(vector<int>& arr, long long low, long long high);

// Поиск и задачи
void sequentialSearch();
void closestPairPoints();
void checkUniqueness();

// Динамическое программирование
void binomialCoefficient();
void warshallAlgorithm();
void floydAlgorithm();

// Математика (НОД)
void gcdComparison();

// Утилиты
long long getArraySize();
long long getGraphSize();
void showMenu();

// Graph data functions
vector<Edge> getKonkovoGraph();
vector<Edge> getArbatGraph();
void printKonkovoVertices();
void printArbatVertices();
void printAdjacencyTable(long long n, const vector<Edge>& edges);

// Kruskal algorithm
bool dfsPath(long long cur, long long target, const vector<vector<pair<long long, long long>>>& adj,
             vector<bool>& visited, vector<long long>& path);
void kruskalShortestPath();

// ============================================================
// ГЛАВНАЯ ФУНКЦИЯ (MAIN)
// ============================================================
int main() {
    srand(time(0)); // Инициализация генератора случайных чисел

    char ch;

    // Бесконечный цикл меню
    do {
        showMenu();
        ch = _getch(); // Считываем нажатие клавиши
        cout << ch << "\n";

        switch (ch) {
            case '1': selectionSort(); break;
            case '2': bubbleSort(); break;
            case '3': sequentialSearch(); break;
            case '4': closestPairPoints(); break;
            case '5': checkUniqueness(); break;
            case '6': gcdComparison(); break;
            case '7': insertionSort(); break;
            case '8': binaryInsertionSort(); break;
            case '9': mergeSort(); break;
            case 'a': quickSort(); break;
            case 'b': binomialCoefficient(); break;
            case 'c': warshallAlgorithm(); break;
            case 'd': floydAlgorithm(); break;
            case 'e': kruskalShortestPath(); break;
            case '0': cout << "Завершение программы...\n"; break;
            default: cout << "Неверный выбор! Нажмите любую клавишу..."; _getch();
        }
        // Пауза перед возвратом в меню (кроме выхода)
        if (ch != '0') {
            cout << "\nНажмите любую клавишу для продолжения...";
            _getch();
        }
    } while (ch != '0');
    return 0;
}

// ============================================================
// ФУНКЦИЯ МЕНЮ
// ============================================================
void showMenu() {
    cout << "\n============ МЕНЮ ===========\n";
    cout << "1. Сортировка выбором\n";
    cout << "2. Пузырьковая сортировка\n";
    cout << "3. Последовательный поиск\n";
    cout << "4. Поиск ближайших точек\n";
    cout << "5. Проверка уникальности элементов\n";
    cout << "6. Сравнение алгоритмов НОД\n";
    cout << "7. Сортировка вставками\n";
    cout << "8. Бинарная сортировка вставками\n";
    cout << "9. Сортировка слиянием (оптимизированная)\n";
    cout << "a. Быстрая сортировка (Quick Sort)\n";
    cout << "b. Вычисление биномиальных коэффициентов\n";
    cout << "c. Алгоритм Воршалла (транзитивное замыкание)\n";
    cout << "d. Алгоритм Флойда (кратчайшие пути для всех пар)\n";
    cout << "e. Алгоритм Крускала + поиск пути в остовном дереве\n";
    cout << "0. Выход из программы\n";
    cout << "==========================\n";
    cout << "Выберите пункт меню: ";
}

// ============================================================
// ПОЛУЧЕНИЕ РАЗМЕРА МАССИВА
// ============================================================
long long getArraySize() {
    int choice;
    cout << "\nВыберите размер массива:\n";
    cout << "1. Малый размер (x < 100)\n";
    cout << "2. Средний размер (100 < x < 10 000)\n";
    cout << "3. Большой размер (10 000 < x < 1 000 000)\n";
    cout << "4. Ввести размер вручную (точное число)\n";
    cout << "Ваш выбор: ";
    cin >> choice;

    long long size;
    switch (choice) {
        case 1: size = rand() % 100 + 10; break;
        case 2: size = rand() % 9900 + 100; break;
        case 3: size = rand() % 990000 + 10000; break;
        case 4:
            cout << "Введите размер массива (положительное целое число): ";
            cin >> size;
            if (size < 1) size = 1;
            break;
        default: cout << "Неверный выбор, используется размер по умолчанию: 100.\n"; size = 100;
    }
    cout << "Размер массива: " << size << "\n";
    return size;
}

// ============================================================
// ПОЛУЧЕНИЕ РАЗМЕРА ГРАФА (для алгоритмов Воршалла и Флойда)
// ============================================================
long long getGraphSize() {
    int choice;
    cout << "\nВыберите количество вершин графа:\n";
    cout << "1. Малое количество (x < 100)\n";
    cout << "2. Среднее количество (100 < x < 1 000)\n";
    cout << "3. Большое количество (1 000 < x < 10 000)\n";
    cout << "4. Очень большое количество (10 000 < x < 100 000)\n";
    cout << "5. Ввести количество вручную (точное число)\n";
    cout << "Ваш выбор: ";
    cin >> choice;

    long long size;
    switch (choice) {
        case 1: size = rand() % 100 + 10; break;
        case 2: size = rand() % 900 + 100; break;
        case 3: size = rand() % 9000 + 1000; break;
        case 4: size = rand() % 90000 + 10000; break;
        case 5:
            cout << "Введите количество вершин (положительное целое число): ";
            cin >> size;
            if (size < 1) size = 1;
            break;
        default: cout << "Неверный выбор, используется значение по умолчанию: 50.\n"; size = 50;
    }
    cout << "Количество вершин: " << size << "\n";
    return size;
}

// ============================================================
// 1. SELECTION SORT (Сортировка выбором)
// ============================================================
void selectionSort() {
    cout << "\n=== СОРТИРОВКА ВЫБОРОМ ====\n";
    long long n = getArraySize();
    vector<int> arr(n);
    for (long long i = 0; i < n; i++) arr[i] = rand() % 10000;
    auto start = high_resolution_clock::now();

    for (long long i = 0; i < n - 1; i++) {
        long long min_idx = i;
        for (long long j = i + 1; j < n; j++) {
            if (arr[j] < arr[min_idx]) min_idx = j;
        }
        if (min_idx != i) swap(arr[i], arr[min_idx]);
    }
    auto stop = high_resolution_clock::now();
    auto duration = duration_cast<microseconds>(stop - start);
    cout << "Массив отсортирован!\n";
    cout << "Время выполнения: " << duration.count() << " микросекунд\n";
    cout << "Первые 10 элементов: ";
    for (int i = 0; i < min(10LL, n); i++) cout << arr[i] << " ";
    cout << "\n";
}

// ============================================================
// 2. BUBBLE SORT (Пузырьковая сортировка)
// ============================================================
void bubbleSort() {
    cout << "\n=== ПУЗЫРЬКОВАЯ СОРТИРОВКА ===\n";
    long long n = getArraySize();
    vector<int> arr(n);
    for (long long i = 0; i < n; i++) arr[i] = rand() % 10000;
    auto start = high_resolution_clock::now();
    for (long long i = 0; i < n - 1; i++) {
        for (long long j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) swap(arr[j], arr[j + 1]);
        }
    }
    auto stop = high_resolution_clock::now();
    auto duration = duration_cast<microseconds>(stop - start);
    cout << "Массив отсортирован!\n";
    cout << "Время выполнения: " << duration.count() << " микросекунд\n";
    cout << "Первые 10 элементов: ";
    for (int i = 0; i < min(10LL, n); i++) cout << arr[i] << " ";
    cout << "\n";
}

// ============================================================
// 3. SEQUENTIAL SEARCH (Последовательный поиск)
// ============================================================
void sequentialSearch() {
    cout << "\n=== ПОСЛЕДОВАТЕЛЬНЫЙ ПОИСК ===\n";
    long long n = getArraySize();
    vector<int> arr(n);
    for (long long i = 0; i < n; i++) arr[i] = rand() % 10000;
    int keyChoice;
    cout << "\nВыберите тип искомого элемента:\n";
    cout << "1. Ввести ключ вручную (может отсутствовать в массиве)\n";
    cout << "2. Использовать ключ, который ТОЧНО есть в массиве\n";
    cout << "Ваш выбор: ";
    cin >> keyChoice;
    int key;

    if (keyChoice == 2) {
        long long randomIndex = rand() % n;
        key = arr[randomIndex];
        cout << "Искомый ключ (из массива): " << key << " (на позиции " << randomIndex << ")\n";
    }
    else {
        cout << "Введите искомый ключ: ";
        cin >> key;
    }

    volatile long long foundIndex = -1;
    auto start = high_resolution_clock::now();
    for (long long i = 0; i < n; i++) {
        if (arr[i] == key) { foundIndex = i; break; }
    }
    auto stop = high_resolution_clock::now();
    auto duration = duration_cast<microseconds>(stop - start);

    cout << "\n--- Результаты ---\n";
    if (foundIndex != -1) cout << "Элемент найден на позиции: " << foundIndex << "\n";
    else cout << "Элемент не найден\n";
    cout << "Время выполнения: " << duration.count() << " микросекунд\n";
    cout << "Первые 10 элементов: ";
    for (int i = 0; i < min(10LL, n); i++) cout << arr[i] << " ";
    cout << "\n";
}

// ============================================================
// 4. CLOSEST PAIR OF POINTS (Поиск ближайших точек)
// ============================================================
void closestPairPoints() {
    cout << "\n=== ПОИСК БЛИЖАЙШЕЙ ПАРЫ ТОЧЕК ===\n";
    long long n = getArraySize();
    vector<pair<double, double>> points(n);
    for (long long i = 0; i < n; i++) {
        points[i].first = (double)(rand() % 10000) / 100.0;
        points[i].second = (double)(rand() % 10000) / 100.0;
    }

    auto start = high_resolution_clock::now();
    double minDist = numeric_limits<double>::max();
    long long idx1 = 0, idx2 = 1;
    for (long long i = 0; i < n - 1; i++) {
        for (long long j = i + 1; j < n; j++) {
            double dx = points[i].first - points[j].first;
            double dy = points[i].second - points[j].second;
            double dist = sqrt(dx * dx + dy * dy);
            if (dist < minDist) { minDist = dist; idx1 = i; idx2 = j; }
        }
    }

    auto stop = high_resolution_clock::now();
    auto duration = duration_cast<microseconds>(stop - start);

    cout << "Ближайшие точки:\n";
    cout << "Точка 1: (" << points[idx1].first << ", " << points[idx1].second << ")\n";
    cout << "Точка 2: (" << points[idx2].first << ", " << points[idx2].second << ")\n";
    cout << "Расстояние: " << minDist << "\n";
    cout << "Время выполнения: " << duration.count() << " микросекунд\n";
}

// ============================================================
// 5. CHECK UNIQUENESS (Проверка уникальности)
// ============================================================
void checkUniqueness() {
    cout << "\n=== ПРОВЕРКА УНИКАЛЬНОСТИ ЭЛЕМЕНТОВ ====\n";
    long long n = getArraySize();
    vector<double> arr(n);
    for (long long i = 0; i < n; i++) arr[i] = (double)(rand() % 10000) / 100.0;
    auto start = high_resolution_clock::now();
    bool isUnique = true;
    for (long long i = 0; i < n - 1; i++) {
        for (long long j = i + 1; j < n; j++) {
            if (arr[i] == arr[j]) {
                isUnique = false;
                goto end_check;
            }
        }
    }
    end_check:
    auto stop = high_resolution_clock::now();
    auto duration = duration_cast<microseconds>(stop - start);
    if (isUnique) cout << "Результат: Все элементы УНИКАЛЬНЫ\n";
    else cout << "Результат: Массив содержит ПОВТОРЯЮЩИЕСЯ элементы \n";
    cout << "Время выполнения: " << duration.count() << " микросекунд\n";
    cout << "Первые 10 элементов: ";
    for (int i = 0; i < min(10LL, n); i++) cout << fixed << setprecision(2) << arr[i] << " ";
    cout << "\n";
}

// ============================================================
// 6. GCD COMPARISON (Сравнение алгоритмов НОД)
// ============================================================
void gcdComparison() {
    int m, n;
    cout << "Введите m: "; cin >> m; cout << endl;
    cout << "Введите n: "; cin >> n; cout << endl;
    int m1 = m, n1 = n, i1 = 0, i2 = 0;
    while (m1 != n1) {
        if (m1 > n1) m1 -= n1; else n1 -= m1;
        i1++;
    }
    cout << "Метод 1 (вычитание): НОД = " << m1 << ", итераций: " << i1;
    cout << endl << endl;
    while (m != 0 && n != 0) {
        if (m > n) m %= n; else n %= m;
        i2++;
    }
    cout << "Метод 2 (деление с остатком): НОД = " << (m + n) << ", итераций: " << i2;
    cout << endl << endl;
    if (i2 < i1) cout << "\nПервый алгоритм быстрее на " << (i1 - i2) << " итераций";
    else if (i2 > i1) cout << "\nВторой алгоритм быстрее на " << (i2 - i1) << " итераций";
    else cout << "\nАлгоритмы показали одинаковую скорость";
    cout << endl << endl;
    system("pause");
}

// ============================================================
// 7. INSERTION SORT (Сортировка вставками)
// ============================================================
void insertionSort() {
    cout << "\n=== СОРТИРОВКА ВСТАВКАМИ ===\n";
    long long n = getArraySize();
    vector<int> arr(n);
    for (long long i = 0; i < n; i++) arr[i] = rand() % 10000;
    auto start = high_resolution_clock::now();
    for (long long i = 1; i < n; i++) {
        int key = arr[i];
        long long j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
    auto stop = high_resolution_clock::now();
    auto duration = duration_cast<microseconds>(stop - start);
    cout << "Массив отсортирован!\n";
    cout << "Время выполнения: " << duration.count() << " микросекунд\n";
    cout << "Первые 10 элементов: ";
    for (int i = 0; i < min(10LL, n); i++) cout << arr[i] << " ";
    cout << "\n";
}

// ============================================================
// 8. BINARY INSERTION SORT (Бинарная сортировка вставками)
// ============================================================
void binaryInsertionSort() {
    cout << "\n=== БИНАРНАЯ СОРТИРОВКА ВСТАВКАМИ ===\n";
    long long n = getArraySize();
    vector<int> arr(n);
    for (long long i = 0; i < n; i++) arr[i] = rand() % 10000;
    auto start = high_resolution_clock::now();
    for (long long i = 1; i < n; i++) {
        int key = arr[i];
        long long left = 0, right = i;
        while (left < right) {
            long long mid = left + (right - left) / 2;
            if (arr[mid] < key) {
                left = mid + 1;
            }
            else {
                right = mid;
            }
        }
        for (long long j = i - 1; j >= left; j--) {
            arr[j + 1] = arr[j];
        }
        arr[left] = key;
    }
    auto stop = high_resolution_clock::now();
    auto duration = duration_cast<microseconds>(stop - start);
    cout << "Массив отсортирован!\n";
    cout << "Время выполнения: " << duration.count() << " микросекунд\n";
    cout << "Первые 10 элементов: ";
    for (int i = 0; i < min(10LL, n); i++) cout << arr[i] << " ";
    cout << "\n";
}

// ============================================================
// 9. MERGE SORT (Оптимизированная сортировка слиянием)
// ============================================================
void mergeOptimized(vector<int>& arr, vector<int>& temp, long long left, long long mid, long long right) {
    long long i = left, j = mid + 1, k = left;
    for (long long idx = left; idx <= right; idx++) temp[idx] = arr[idx];
    while (i <= mid && j <= right) {
        if (temp[i] <= temp[j]) arr[k++] = temp[i++];
        else arr[k++] = temp[j++];
    }
    while (i <= mid) arr[k++] = temp[i++];
}

void mergeSortRecursiveOpt(vector<int>& arr, vector<int>& temp, long long left, long long right) {
    if (left < right) {
        long long mid = left + (right - left) / 2;
        mergeSortRecursiveOpt(arr, temp, left, mid);
        mergeSortRecursiveOpt(arr, temp, mid + 1, right);
        mergeOptimized(arr, temp, left, mid, right);
    }
}

void mergeSort() {
    cout << "\n=== СОРТИРОВКА СЛИЯНИЕМ (ОПТИМИЗИРОВАННАЯ) ===\n";
    long long n = getArraySize();
    vector<int> arr(n);
    for (long long i = 0; i < n; i++) arr[i] = rand() % 10000;
    vector<int> temp(n);
    auto start = high_resolution_clock::now();
    mergeSortRecursiveOpt(arr, temp, 0, n - 1);
    auto stop = high_resolution_clock::now();
    auto duration = duration_cast<microseconds>(stop - start);
    cout << "Массив отсортирован!\n";
    cout << "Время выполнения: " << duration.count() << " микросекунд!\n";
    cout << "Первые 10 элементов: ";
    for (int i = 0; i < min(10LL, n); i++) cout << arr[i] << " ";
    cout << "\n";
}

// ============================================================
// 10. QUICK SORT (Быстрая сортировка)
// ============================================================
long long partition(vector<int>& arr, long long low, long long high) {
    int pivot = arr[high];
    long long i = low - 1;
    for (long long j = low; j < high; j++) {
        if (arr[j] <= pivot) {
            i++;
            swap(arr[i], arr[j]);
        }
    }
    swap(arr[i + 1], arr[high]);
    return i + 1;
}

void quickSortRecursive(vector<int>& arr, long long low, long long high) {
    if (low < high) {
        long long pi = partition(arr, low, high);
        quickSortRecursive(arr, low, pi - 1);
        quickSortRecursive(arr, pi + 1, high);
    }
}

void quickSort() {
    cout << "\n=== БЫСТРАЯ СОРТИРОВКА (QUICK SORT) ===\n";
    long long n = getArraySize();
    vector<int> arr(n);
    for (long long i = 0; i < n; i++) arr[i] = rand() % 10000;
    auto start = high_resolution_clock::now();
    quickSortRecursive(arr, 0, n - 1);
    auto stop = high_resolution_clock::now();
    auto duration = duration_cast<microseconds>(stop - start);
    cout << "Массив отсортирован!\n";
    cout << "Время выполнения: " << duration.count() << " микросекунд\n";
    cout << "Первые 10 элементов: ";
    for (int i = 0; i < min(10LL, n); i++) cout << arr[i] << " ";
    cout << "\n";
}

// ============================================================
// 11. BINOMIAL COEFFICIENT (Биномиальные коэффициенты)
// ============================================================
long long binomial(int n, int k) {
    if (k < 0 || k > n) return 0;
    if (k == 0 || k == n) return 1;
    if (k > n - k) k = n - k;

    vector<vector<long long>> C(n + 1, vector<long long>(k + 1, 0));
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= min(i, k); j++) {
            if (j == 0 || j == i) C[i][j] = 1;
            else C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
        }
    }
    return C[n][k];
}

void binomialCoefficient() {
    cout << "\n=== ВЫЧИСЛЕНИЕ БИНОМИАЛЬНЫХ КОЭФФИЦИЕНТОВ ===\n";

    int choice;
    cout << "\nВыберите способ задания n и k:\n";
    cout << "1. Случайные числа (x < 100)\n";
    cout << "2. Случайные числа (100 < x < 1 000)\n";
    cout << "3. Случайные числа (1 000 < x < 10 000)\n";
    cout << "4. Случайные числа (10 000 < x < 100 000)\n";
    cout << "5. Ввести значения вручную\n";
    cout << "Ваш выбор: ";
    cin >> choice;

    int n, k;
    if (choice == 5) {
        cout << "Введите n: ";
        cin >> n;
        cout << "Введите k (0 <= k <= n): ";
        cin >> k;
        if (k < 0 || k > n) {
            cout << "Ошибка: k должно быть в диапазоне [0, n]\n";
            return;
        }
    }
    else {
        long long maxVal;
        switch (choice) {
            case 1: maxVal = rand() % 100; break;
            case 2: maxVal = rand() % 900 + 100; break;
            case 3: maxVal = rand() % 9000 + 1000; break;
            case 4: maxVal = rand() % 90000 + 10000; break;
            default: maxVal = 50;
        }
        n = maxVal;
        k = rand() % (n + 1);
    }
    cout << "\nСгенерированные значения: n = " << n << ", k = " << k << "\n";
    if (n > 60) {
        cout << "Предупреждение: при n > 60 результат может переполнить тип long long.\n";
    }

    auto start = high_resolution_clock::now();
    long long result = binomial(n, k);
    auto stop = high_resolution_clock::now();
    auto duration = duration_cast<microseconds>(stop - start);
    cout << "\nC(" << n << ", " << k << ") = " << result << "\n";
    cout << "Время выполнения: " << duration.count() << " микросекунд\n";

    if (n <= 20) {
        cout << "\nСтрока треугольника Паскаля для n = " << n << ":\n";
        for (int i = 0; i <= n; i++) {
            cout << binomial(n, i) << " ";
        }
        cout << "\n";
    }
    else {
        cout << "\n(Вывод строки треугольника Паскаля пропущен для n > 20)\n";
    }
}

// ============================================================
// 12. WARSHALL ALGORITHM (Алгоритм Воршалла)
// ============================================================
void warshallAlgorithm() {
    cout << "\n=== АЛГОРИТМ ВОРШАЛЛА (ТРАНЗИТИВНОЕ ЗАМЫКАНИЕ) ===\n";
    long long n = getGraphSize();

    // Создаём случайную матрицу смежности
    vector<vector<int>> R(n, vector<int>(n, 0));
    for (long long i = 0; i < n; i++) {
        R[i][i] = 1;
        for (long long j = 0; j < n; j++) {
            if (i != j && rand() % 3 == 0) {
                R[i][j] = 1;
            }
        }
    }

    auto start = high_resolution_clock::now();
    for (long long k = 0; k < n; k++) {
        for (long long i = 0; i < n; i++) {
            if (R[i][k] == 0) continue;
            for (long long j = 0; j < n; j++) {
                if (R[k][j] == 1) {
                    R[i][j] = 1;
                }
            }
        }
    }
    auto stop = high_resolution_clock::now();
    auto duration = duration_cast<microseconds>(stop - start);
    cout << "Время выполнения: " << duration.count() << " микросекунд\n";
}

// ============================================================
// 13. FLOYD ALGORITHM (Алгоритм Флойда)
// ============================================================
void floydAlgorithm() {
    cout << "\n=== АЛГОРИТМ ФЛОЙДА (КРАТЧАЙШИЕ ПУТИ ДЛЯ ВСЕХ ПАР ВЕРШИН) ===\n";
    long long n = getGraphSize();
    const int INF = 1000000;
    vector<vector<int>> D(n, vector<int>(n, INF));
    for (long long i = 0; i < n; i++) {
        D[i][i] = 0;
        for (long long j = 0; j < n; j++) {
            if (i != j && rand() % 4 == 0) {
                D[i][j] = rand() % 100 + 1;
            }
        }
    }

    auto start = high_resolution_clock::now();
    for (long long k = 0; k < n; k++) {
        for (long long i = 0; i < n; i++) {
            for (long long j = 0; j < n; j++) {
                if (D[i][k] < INF && D[k][j] < INF) {
                    D[i][j] = min(D[i][j], D[i][k] + D[k][j]);
                }
            }
        }
    }
    auto stop = high_resolution_clock::now();
    auto duration = duration_cast<microseconds>(stop - start);

    long long reachable = 0;
    long long totalDist = 0;
    for (long long i = 0; i < n; i++) {
        for (long long j = 0; j < n; j++) {
            if (i != j && D[i][j] < INF) {
                reachable++;
                totalDist += D[i][j];
            }
        }
    }

    cout << "Кратчайшие пути вычислены!\n";
    cout << "Достижимых пар вершин: " << reachable << " из " << (n * (n - 1)) << "\n";
    if (reachable > 0) {
        cout << "Средняя длина пути: " << fixed << setprecision(2) << (double)totalDist / reachable << "\n";
    }
    cout << "Время выполнения: " << duration.count() << " микросекунд\n";

    if (n <= 10) {
        cout << "\nМатрица расстояний (первые " << min(10LL, n) << "x" << min(10LL, n) << "):\n";
        for (int i = 0; i < min(10LL, n); i++) {
            for (int j = 0; j < min(10LL, n); j++) {
                if (D[i][j] == INF)
                    cout << " ∞ ";
                else
                    cout << setw(3) << D[i][j] << " ";
            }
            cout << "\n";
        }
    }
}

// ============================================================
// 14. KRUSKAL SHORTEST PATH (Алгоритм Крускала + поиск пути в остовном дереве)
// ============================================================

// DFS для поиска пути в дереве
bool dfsPath(long long cur, long long target, const vector<vector<pair<long long, long long>>>& adj,
             vector<bool>& visited, vector<long long>& path) {
    if (cur == target) {
        path.push_back(cur);
        return true;
    }
    visited[cur] = true;
    path.push_back(cur);
    for (const auto& neighbor : adj[cur]) {
        long long nxt = neighbor.first;
        if (!visited[nxt]) {
            if (dfsPath(nxt, target, adj, visited, path))
                return true;
        }
    }
    path.pop_back();
    return false;
}

// Вывод описания вершин для Коньково
void printKonkovoVertices() {
    cout << "\n=== ВЕРШИНЫ ГРАФА: КОНЬКОВО ===\n";
    cout << "1 - Обручева × Профсоюзная (запад)\n";
    cout << "2 - Обручева × Миклухо-Маклая\n";
    cout << "3 - Миклухо-Маклая × Островитянова (юг)\n";
    cout << "4 - Островитянова × Введенского (юг)\n";
    cout << "5 - Введенского × Академика Волгина\n";
    cout << "6 - Академика Волгина × Островитянова (восток)\n";
    cout << "7 - Миклухо-Маклая × Бутлерова (юг)\n";
    cout << "8 - Миклухо-Маклая × Профсоюзная (центр)\n";
    cout << "9 - Профсоюзная × Обручева (запад)\n";
    cout << "10 - Профсоюзная × Обручева (север)\n";
    cout << "11 - Бутлерова × Островитянова (центр)\n";
    cout << "12 - Островитянова × Бутлерова (восток)\n";
    cout << "13 - Севастопольский × Академика Волгина (восток)\n";
    cout << "14 - Островитянова × Профсоюзная (восток)\n";
    cout << "15 - Профсоюзная × Миклухо-Маклая (север)\n";
    cout << "16 - Обручева × Профсоюзная (северо-восток)\n";
    cout << "17 - Профсоюзная × Обручева (восток)\n";
    cout << "18 - Профсоюзная × Севастопольский (северо-восток)\n";
    cout << "19 - Севастопольский проспект (восточная граница)\n";
}

// Вывод описания вершин для Арбата
void printArbatVertices() {
    cout << "\n=== ВЕРШИНЫ ГРАФА: АРБАТ ===\n";
    cout << "1 - Смоленская ул. × набережная (юго-запад)\n";
    cout << "2 - Смоленская ул. × Новинский бульвар (юг-центр)\n";
    cout << "3 - Новый Арбат × Смоленская ул. (запад-центр)\n";
    cout << "4 - Новый Арбат × ул. Арбат (Арбатские Ворота, центр)\n";
    cout << "5 - ул. Арбат × Арбатская пл. (центр-восток)\n";
    cout << "6 - Арбатская пл. × Воздвиженка (восток)\n";
    cout << "7 - Новый Арбат × Поварская ул. (север)\n";
}

// Получение графа Коньково
vector<Edge> getKonkovoGraph() {
    return {
        Edge(1, 2, 200), Edge(1, 9, 700),
        Edge(2, 8, 700), Edge(2, 3, 800),
        Edge(3, 7, 350), Edge(3, 4, 200),
        Edge(4, 6, 500), Edge(4, 5, 600),
        Edge(9, 8, 200), Edge(8, 7, 450), Edge(8, 10, 600),
        Edge(7, 11, 200), Edge(7, 6, 350),
        Edge(6, 5, 200), Edge(6, 12, 200),
        Edge(5, 13, 400),
        Edge(11, 12, 350), Edge(11, 15, 200),
        Edge(12, 14, 200),
        Edge(13, 14, 250), Edge(13, 19, 600),
        Edge(14, 15, 350), Edge(14, 18, 300),
        Edge(15, 10, 750), Edge(15, 17, 300),
        Edge(10, 16, 100),
        Edge(16, 17, 300),
        Edge(17, 18, 300),
        Edge(18, 19, 300)
    };
}

// Получение графа Арбата
vector<Edge> getArbatGraph() {
    return {
        Edge(1, 2, 360), Edge(1, 3, 420), Edge(1, 4, 520), Edge(6, 7, 750),
        Edge(2, 3, 500), Edge(2, 4, 380), Edge(2, 5, 790), Edge(2, 6, 810),
        Edge(3, 4, 450), Edge(3, 7, 550),
        Edge(4, 5, 650), Edge(4, 7, 500),
        Edge(5, 6, 60), Edge(5, 7, 700)
    };
}

// Вывод матрицы смежности с выровненными столбцами
void printAdjacencyTable(long long n, const vector<Edge>& edges) {
    cout << "\n=== МАТРИЦА СМЕЖНОСТИ (ИСХОДНЫЙ ГРАФ) ===\n";

    vector<vector<long long>> matrix(n + 1, vector<long long>(n + 1, 0));

    for (const auto& e : edges) {
        matrix[e.u][e.v] = e.weight;
        matrix[e.v][e.u] = e.weight;
    }

    const int CELL_WIDTH = 5;

    cout << "   |";
    for (long long j = 1; j <= n; j++) {
        cout << setw(CELL_WIDTH) << j;
    }
    cout << "\n";

    cout << "---+";
    for (long long j = 1; j <= n; j++) {
        cout << string(CELL_WIDTH, '-');
    }
    cout << "\n";

    for (long long i = 1; i <= n; i++) {
        cout << setw(2) << i << " |";
        for (long long j = 1; j <= n; j++) {
            if (matrix[i][j] == 0)
                cout << setw(CELL_WIDTH) << "0";
            else
                cout << setw(CELL_WIDTH) << matrix[i][j];
        }
        cout << "\n";
    }
}

void kruskalShortestPath() {
    cout << "\n=== АЛГОРИТМ КРУСКАЛА + ПОИСК ПУТИ ===\n";

    int graphChoice;
    cout << "\nВыберите граф:\n";
    cout << "1. Коньково\n";
    cout << "2. Арбат\n";
    cout << "Ваш выбор: ";
    cin >> graphChoice;

    long long n;
    vector<Edge> edges;

    if (graphChoice == 1) {
        n = 19;
        edges = getKonkovoGraph();
        printKonkovoVertices();
    }
    else {
        n = 7;
        edges = getArbatGraph();
        printArbatVertices();
    }

    printAdjacencyTable(n, edges);

    // === КРУСКАЛ: построение минимального остовного дерева ===
    vector<Edge> sortedEdges = edges;
    sort(sortedEdges.begin(), sortedEdges.end());

    DSU dsu(n);
    vector<Edge> mstEdges;
    long long mstWeight = 0;

    for (const auto& e : sortedEdges) {
        if (dsu.unite(e.u, e.v)) {
            mstEdges.push_back(e);
            mstWeight += e.weight;
            if (mstEdges.size() == n - 1) break;
        }
    }

    cout << "\n=== МИНИМАЛЬНОЕ ОСТОВНОЕ ДЕРЕВО (MST) ===\n";
    cout << "Рёбра остовного дерева:\n";
    for (const auto& e : mstEdges) {
        cout << e.u << " --" << e.weight << "-- " << e.v << "\n";
    }

    // Построение списка смежности для MST
    vector<vector<pair<long long, long long>>> mstAdj(n + 1);
    for (const auto& e : mstEdges) {
        mstAdj[e.u].push_back({e.v, e.weight});
        mstAdj[e.v].push_back({e.u, e.weight});
    }

    // Выбор вершин для поиска пути
    long long start, end;
    cout << "\n=== ПОИСК ПУТИ В ОСТОВНОМ ДЕРЕВЕ ===\n";
    cout << "Введите начальную вершину (1.." << n << "): ";
    cin >> start;
    cout << "Введите конечную вершину (1.." << n << "): ";
    cin >> end;

    if (start < 1 || start > n || end < 1 || end > n) {
        cout << "Ошибка: неверный номер вершины!\n";
        return;
    }

    // DFS для поиска пути
    vector<bool> visited(n + 1, false);
    vector<long long> path;

    if (dfsPath(start, end, mstAdj, visited, path)) {
        cout << "\nПуть найден в остовном дереве:\n";
        cout << "Маршрут: ";
        for (size_t i = 0; i < path.size(); i++) {
            cout << path[i];
            if (i < path.size() - 1) cout << " -> ";
        }
        cout << "\n";

        long long pathWeight = 0;
        for (size_t i = 0; i < path.size() - 1; i++) {
            for (const auto& neighbor : mstAdj[path[i]]) {
                long long v = neighbor.first;
                long long w = neighbor.second;
                if (v == path[i + 1]) {
                    pathWeight += w;
                    break;
                }
            }
        }
        cout << "Длина пути в остовном дереве: " << pathWeight << " м\n";
        cout << "\nПРЕДУПРЕЖДЕНИЕ:\n";
        cout << "Этот путь минимален в рамках остовного дерева,\n";
        cout << "но не обязательно является кратчайшим в исходном графе.\n";
    }
    else {
        cout << "X Путь не найден (граф несвязный)\n";
    }
}